社区发现算法之Louvain算法

Louvain（鲁汶）算法是由比利时鲁汶大学的 Vincent D.Blondel 等人在08年的论文”Fast Unfolding of Communities in Large Networks”中提出的，也是以最大化模块度为目标的一种启发式迭代方法（Heuristic Algorithm），因其能以较高的计算效率得到不错的社区划分结果，是近年来最多被提及和使用的社区发现算法。回忆下模块度的定义，它是指一个边数占网络总边数的比例，而其中的边数是指同一个社区内的实际边数与具有相同节点度分布的随机情况下的期望边数的差值。

为了方便说明鲁汶算法的迭代过程，我们对模块度的形式作个变换，将以上标红的部分换一种写法：

鲁汶算法的迭代过程

其基本思想是将某个节点调整到其他社区后所带来的模块度增益计算出来，根据增益情况来决定是否要重新划分该节点的归属社区，可分为如下两个阶段：

• 第一阶段：社区迭代

1）初始化，将图中的每个节点 i 看作一个单独的社区，计算 Q 值。

2）对于每一个节点 i，尝试将其依次划分到与它相邻的各个社区 c，然后计算更新后的社区 c 的 Q 值与划分前的 Q 值（社区 i + 社区 c）之差，从中找出能产生最大模块度增益 ΔQ 的相邻社区进行更新。如果 Q 值增益过小，那就维持社区原状。

3）重复2）这个过程，直到所有节点的所属社区不再变化。不过论文中有提到这里节点的划分顺序对最终模块度的结果影响不大，但是会影响计算时间。ΔQ 的计算逻辑如下：

ΔQ 的计算公式可分为两部分，前半部分是节点 i 移动到社区 c 之后的模块度，后半部分是移动之前社区 c 和社区 i 的模块度。通过以上最终的化简形式也可以看到，实际使用过程只需计算一个非常简单的模块就可以了。可以看到整个计算过程都是把 i 当作孤立点来看，不过这里小伍哥也曾提出一点困惑，就是 ΔQ 没有考虑到节点 i 从原来归属社区删除的这个影响，因为在后面的划分迭代中，i 可能被分到有多个节点的社区中，而不是初始化下的单节点状态。

• 第二阶段：社区压缩再迭代

第一阶段结束后，将此时图中所有在同一个社区的节点压缩成一个新节点（超节点），在得到的这张新图中重新计算超节点的权重度，然后将超节点当成普通节点应用上面第一阶段的过程并进行迭代，直到整个图的模块度不再增加。

这里需要注意的是超节点对应的原社区内部存在边，因此超节点会有两种权重度需要计算，一个是环权重，由对应社区的内部边的权重汇总而来，一个是边权重，计算就基于对应社区之间的边权重了。以论文中的这张图为例，通过第一阶段的计算得到四个不同的社区，压缩之后变成了由四个超节点组成的新图。

从流程来看，社区内的点在压缩后将作为一个整体进行模块度优化的计算，而且不再拆分，从而能够产生层次性的社区结构。这期间计算耗时较多的是最底一层的社区划分，因为节点按社区压缩后，将大大缩小边和节点数目，并且计算节点 i 分配到其相邻社区 c 时模块度的变化只与节点 i、社区 c 有关，与其他社区无关，因此计算很快。

算法步骤的可视化以论文中的图为例，每一轮都由前面提到的两个阶段组成，一个可以理解为通过社区的局部变化来优化模块度，另一个是聚合已发现的社区，建立一个新的社区网络，然后迭代地重复这些过程，直到模块度不可能增加为止。

一些基本概念

1. 权重度

鲁汶算法在计算模块度时用到了节点权重度和社区权重度两个概念。

• 节点权重度，该节点所有连边的权重和，包括该点的邻边（连接至其它点）以及自环边（连接至该点自身）。如下图，红色节点有三条邻边和一条自环边，该点的权重度为 6 = 1 + 0.5 + 3 + 1.5（注意：自环边的权重只被计算1次）。

图源：ultipa

• 社区权重度，是指一个社区内所有节点权重度的和。
• 社区内部权重度，是指仅考虑两个端点均在该社区内的边的情况，也就是从该社区的权重度中去掉该社区和其它社区之间的边的权重。
• 全图权重度，是指图中所有节点权重度的和。如果将全图划分为多个社区，由于图中每个点属于并且仅属于一个社区，全图权重度也等于这些社区权重度的和。

2. 社区压缩

社区压缩是将社区内的所有节点用一个聚合节点来表示，该社区的内部权重度即为此聚合点的自环边权重，每两个社区之间的边权重和即为相应两个聚合点之间的边权重。在不改变局部权重度以及全图权重度的前提下，社区压缩通过尽可能地减少点、边数量来提高后续迭代的速度。

3. 特殊处理

• 孤点、不连通图

对于孤点，无论经过多少轮迭代都无法和其它节点合并，因为孤点与其他任何节点的边权重都为 0，合并后不会给模块度带来增益。而对于不连通图，各个连通分量之间没有邻边，不同连通分量内的点不能合并，因此各个不连通的区域都是独立的社区，鲁汶算法的社区划分仅在连通分量内部有意义。

• 有向边

对于有向边，鲁汶算法会忽略边的方向，按照无向边进行计算。