The fast unfolding of communities in large networks

这篇论文是关于大规模网络的社群划分的一种快速算法。

介绍部分

网络的社群划分需要把节点变成紧密连接的节点和稀疏分散的节点， 其中紧密连接的节点属于同一个社群， 稀疏节点属于不同社群。 当需要精确求解时, 这个问题被认识时一个计算互相作用的问题.

目前大致可以把不同类型的社群检测算法分为两类: 一类是可分算法, 检测社群内部的节点和链接并且将它们适当的从网络中进行删除; 另一类算法可以认为是聚类算法, 递归地将相似的节点或者社群连接到一起, 并且通过最大化一个目标函数来完成聚类的过程.

上述算法对于社群监测的好坏可以通过一个叫做模块度的张量进行衡量.

$$ Q =\frac{1}{2m} [A_{ij}-\frac{k_i}{k_j}{2m}]\delta(c_i,c_j) $$

上述公式可以进行简化,

$$Q= \frac{1}{2m} [\Sigma_{in} -\frac{[\Sigma_{total}]^2}{2m}]$$

Louvain算法

Louvain算法的思想非常简单, 就是反复进行迭代.

迭代过程如下:

初始化: 将每个节点看成一个社群

1. 对网络中的每个节点, 计算如果移动到相连的其它社群中, $\delta Q$, $\delta Q$最大的群非负则移动, 否则不移动.
2. 网络不再改变的时候进行压缩.