团伙挖掘：Blondel Louvain 模块度（1）

（一）社区检测的核心目标

网络社区指“内部链接密集、外部链接稀疏”的子单元，社区检测的核心是通过算法划分网络结构，揭示节点间的聚合规律。Louvain算法的设计目标，正是解决传统算法在超大规模网络中“处理慢、精度低”的痛点，其有效性已在200万用户的比利时移动网络、1.18亿节点的网页图中得到验证（Blondel et al., 2008）。

（二）质量衡量标准：模块化Q

论文明确指出，社区划分质量常以“模块化（Modularity）”衡量，该指标取值范围为-1至1，核心作用是量化“社区内链接密度与社区间链接密度的差异”（Blondel et al., 2008）。

The modularity of a partition is a scalar value between -1 and 1 that measures the density of links inside communities as compared to links between communities (Blondel et al., 2008).

简言之，模块化Q值越接近1，说明社区内部链接越紧密、外部关联越稀疏，划分结果越优。这一指标是Louvain算法迭代优化的核心目标。

（一）阶段1：节点社区的局部优化

初始状态下，每个节点被分配为独立社区，即网络中有N个节点就有N个社区。随后对每个节点i执行以下操作：

1. 遍历节点i的所有邻居节点j，计算将i从当前社区移除并加入j所在社区后的模块化变化量ΔQ；

2. 将i归入ΔQ最大且为正的社区，若所有ΔQ均为负，则i保留在原社区；

3. 重复上述过程，直至所有节点的移动都无法提升模块化，完成一次局部优化。

需注意的是，节点的处理顺序会影响算法输出结果，因此初始化阶段的节点排序设计具有实际意义（Blondel et al., 2008）。这一步的核心价值是通过单节点的精细调整，避免小社区被误合并，缓解模块化“分辨率限制”问题。

（二）阶段2：社区的全局聚合

将阶段1得到的每个社区视为“超级节点”，构建新的元网络：

• 新节点间的链接权重 = 原网络中对应两个社区内所有节点间链接的权重总和；

• 同一社区内部的链接权重，转化为对应超级节点的自环权重。

完成聚合后，对元网络重复阶段1的节点调整操作，形成“局部优化-全局聚合”的循环，直至网络结构不再变化，迭代终止。

（一）ΔQ计算公式

将孤立节点i移入社区C后，ΔQ的计算公式为：

\(\Delta Q=\left[\frac{\sum_{\text {in }}+2 k_{i, \text { in }}}{2 m}-\left(\frac{\sum_{\text {tot }}+k_{i}}{2 m}\right)^{2}\right]-\left[\frac{\sum_{\text {in }}}{2 m}-\left(\frac{\sum_{\text {tot }}}{2 m}\right)^{2}-\left(\frac{k_{i}}{2 m}\right)^{2}\right]\)

公式中各参数定义如下（Blondel et al., 2008）：

• \(\sum_{\text {in }}\) ：社区C内部所有链接的权重总和；

• \(\sum_{\text {tot }}\) ：社区C中所有节点与网络中其他节点链接的权重总和；

• \(k_{i}\) ：节点i与网络中所有节点链接的权重总和；

• \(k_{i, \text { in }}\) ：节点i与社区C内节点链接的权重总和；

• \(m\) ：整个网络中所有链接的权重总和。

（二）ΔQ的本质解读

ΔQ的计算逻辑可概括为“合并后总模块化 - 合并前各部分模块化之和”，与“train twice”的思想相通——先计算节点i独立存在时的模块化贡献、社区C的模块化贡献，再计算两者合并后的总贡献，差值即为ΔQ（轩辕森, 2017）。

模块度增量delta Q，即把一个孤立的点放入一个社区C后，计算Modularity的变化，其中计算过程的要点是，首先计算1个点的Modularity，和社区C的Modularity，再计算合并后新社区的Modularity，新社区的Modularity减去前两个Modularity就是delta Q（轩辕森, 2017）。

当ΔQ为正时，节点i加入社区C能提升整体模块化，说明该移动符合“社区内部密集”的核心特征；ΔQ为负时则相反，节点需保留原社区。

（一）超大规模网络性能

论文通过两类典型案例验证算法效率（Blondel et al., 2008）：

This is shown first by identifying language communities in a Belgian mobile phone network of 2 million customers and by analyzing a web graph of 118 million nodes and more than one billion links.

在实际工程测试中，该算法效率优势更显著：针对70万节点、200万边的网络，迭代至收敛仅需1.77秒（xsqlx, 2018）。实际应用中，还可通过设置“节点稳定比例阈值”提前终止迭代，进一步提升效率，无需等待所有节点完全不再变化（xsqlx, 2018）。

（二）代码实现与资源

Louvain算法的开源实现资源丰富，便于工程落地：

• C语言实现：https://github.com/liuzhiqiangruc/dml/blob/master/cls/louvain.c（xsqlx, 2018）；

• Python工具包：scikit-network库提供成熟的Louvain聚类接口，可直接调用（https://scikit-network.readthedocs.io/en/latest/tutorials/clustering/louvain.html）。