复杂网络社区发现算法---Fast Unfolding

2018-06-10

参考论文: Fast unfolding of communities in large networks (2008)

模块度定义

$$
Q = \frac{1}{2m}\sum_{i,j}[A_{i,j} - \frac{k_ik_j}{2m}]\delta(c_i,c_j)
$$

m是图G中总的边数，2m显然就是总的度数

A是一个边权矩阵，$A_{i,j}$表示i和j之间的边权。ki表示点i的度数。ci表示i点所属的社区

$\delta(c_i,c_j)$表示i，j属于相同社区时为1，否则为0

那么上式很容易转化为
$$
Q = \sum_c(\frac{\sum_{in}}{2m}-(\frac{\sum_{tot}}{2m})^2)
$$
$\sum_{in}$表示社区为c的点之间的总度数。比如点1,2,3属于社区1，那么1-2,1-3,2-3，那么内连接度数为6，如果有1-4的连接边，4不属于社区1就不用考虑了。

$\sum_{tot}$表示社区为c的点的总度数之和。比如点1,2,3属于社区1,存在边1-2,1-3,1-4,2-3，那么总的度数就是d(1)+d(2)+d(3) = 3+2+2=7

这两个式子等价很显然，简单可证。前半部分很容易理解

后半部分主要是,还是根据上述假设，则变成
$$
\frac{(k_1+k_2+k_3)*(k_1+k_2+k_3) }{2m} => \frac{\sum_{tot}}{2m}
$$

模块度变化差值

当一个独立点加入到相邻点的社区当中，根据上述转化后的式子很容易得知模块度变化为
$$
\Delta Q = [\frac{\sum_{in} + k_{i,in}}{2m}-(\frac{\sum_{tot}+k_i}{2m})^2] - [\frac{\sum_{in}}{2m}-(\frac{\sum_{tot}}{2m})^2-(\frac{k_i}{2m})^2]
$$
前半部分是变化之后对应部分的Q值，后半部分是变化前对应部分的Q值。这里保证点i是独立的，否则后半部分不成立。

所以根据这个很显然，如果i加入到社区c，加入c是一个单独的点，但由于i的加入它，c之后不能作为变化点出现，这个在写代码过程中非常重要。

算法流程

对于每一个点u，尝试加入到它相邻点的社区当中，找到一个加入的社区使得$\Delta Q$最大。如果$\Delta Q$均小于0，那就保持原社区不变。
对所有点都访问过一次。如果整个过程没有进行任何更新，那就认为已经达到了贪心下的最优社区划分。如果还未达到最优，那么将所有相同社区的点缩成一个点，重新构建图，继续按照第一步执行。