Louvain算法
简介
Louvain算法是基于模块度的社区发现算法，能够发现层次性的社区结构，其优化目标是最大化整个社区网络的模块度。其算法论文发表自2008年，原文为Fast unfolding of communities in large networks。
模块度(Modularity)
模块度是评估一个社区网络划分好坏的度量方法。
模块度的定义社区内节点之间的实际连边数与随机情况下连边数的差值。其物理意义是：模块度越大，同一个社区内的节点之间联系更加紧密，不同社区之间的节点联系更加松散。
对于一个有 \(n\) 个节点， \(m\) 条边的网络，其中节点 \(v\) 有 \(k_v\) 条边(即节点 \(v\) 的度为 \(k_v\))，其模块度公式定义如下:
\[ \begin{aligned} Q = \frac{1}{2m} \sum_{i,j} \lbrack A_{ij} - \frac{k_i k_j}{2m} \rbrack \\ \delta(u,v) = \{_{0\ else}^{1 when\ u == v} \end{aligned} \]
其中
- \(A_{ij}\) 表示节点 \(i\) 和节点 \(j\) 之间的权重，当网络为无权图，权重均为1、
- \(k_i = \sum_{j} A_{ij}\) 即节点 \(i\) 的权重之和(无权图即度数)
- \(c_i\) 表示节点 \(i\) 所属社区
- \(m = \frac{1}{2}\sum_{i,j} A_{ij}\)即所有边权重之和(无权图即边的数量)
公式内部 \(A_{ij} - \frac{k_i k_j}{2m}\) 代表节点 \(i\) 与 节点 \(j\) 相连实际与期望的差, \(\frac{k_i k_j}{2m}\) 表示节点 \(i\) 与 节点 \(j\) 在 2m 个边节点中存在 \(k_i k_j\) 个可能。
设 \(\sum in\) 代表社区 \(c\) 内的边权重之和, \(\sum tot\) 代表与社区 \(c\) 内的节点相连的变权重之和。
\[ \begin{aligned} Q &= \frac{1}{2m}[\sum_{i,j}A_{ij} - \frac{\sum_ik_i\sum_jk_j}{2m}]\delta(c_i,c_j) \\ &= \sum_{c} \lbrack \frac{\sum in}{2m} - (\frac{\sum tot}{2m})^2 \rbrack \\ &= \sum_{c} \lbrack e_c - a_c^2 \rbrack \end{aligned} \]
这样模块度可以理解为 社区内部边的权重和 减去 所有与社区内节点相连的边的权重和 的平方。对于无权图，模块度为 社区内部的度数 减去 社区内节点的总度数 的平方。
算法实现
算法步骤
- 初始化图中节点均为一个独立社区(即节点数为社区数)
- 对于每个节点 \(i\) 依次将其分配到其邻居所属社区，计算分配前后模块度差值的 \(Q_{cur} - Q_{pre}\), 将节点 \(i\) 分配至 差值大于0且最大 的邻居所属社区中, 否则保持不变
- 重复步骤2，直至所有节点的所属社区不在变化
- 对图进行压缩, 所有在同一社区的节点压缩成一个新的节点，此时边权等均可能发生变化
- 重复步骤1，直至整个图的模块度无法增益
从步骤中可以看出步骤2中节点顺序对分群结果有所影响，其中步骤二的公式如下
\[ \begin{aligned} \Delta Q &= \lbrack \frac{\sum_{in}+k_{i,in}}{2m}-(\frac{\sum_{tot}+k_i}{2m})^2 \rbrack- \lbrack \frac{\sum_{in}}{2m}-(\frac{\sum_{tot}}{2m})^2-(\frac{k_i}{2m})^2 \rbrack \\ &= \lbrack \frac{k_{i,in}}{2m}-\frac{\sum_{tot}k_i}{2m^2} \rbrack \end{aligned} \]
其中 \(k_{i,in}\) 是社区 \(c\) 内节点与节点 \(i\) 的边权重之和，注意 \(k_{i,in}\) 纳入内部时同时存在原内部节点到节点 \(i\) 与节点 \(i\) 到原内部节点的权重，因此对应边权重加起来再乘以2。
分了两部分，前面部分表示把节点i加入到社区c后的模块度，后一部分是节点i作为一个独立社区和社区c的模块度，这里有一个困惑我的地方，虽然我按照这个公式实现的分群算法效果很好，但是我认为𝐷𝑒𝑙𝑡𝑎𝑄 少了把节点i从其原来社区删除这一步，因为后面的划分时，节点i所在的社区可能有多个节点。