第三章 Louvain算法回顾：两阶段迭代与模块度增益
聊Leiden之前，我觉得有必要先把Louvain算法拉出来好好捋一捋。毕竟Leiden就是站在Louvain的肩膀上改进的，不了解Louvain的痛处，你就不知道Leiden到底牛在哪。
3.1 Louvain算法想解决什么问题？
社区检测这个老问题，说白了就是想把网络里抱团的节点找出来。但现实中的网络往往大得吓人——几百万个节点、上亿条边都是家常便饭。传统的谱聚类方法，算个特征向量都能让服务器直接挂掉。
Louvain算法的厉害之处在于：它能在不牺牲太多精度的前提下，把时间复杂度压到接近线性。我在一个千万级节点的社交网络项目里试过，跑一次全图社区检测，普通服务器上也就几十秒。嗯，这个效率在当时确实惊艳到我了。
3.2 核心思想：两阶段迭代
Louvain算法的精髓就四个字：两阶段迭代。每次迭代分两步走：
- 局部移动阶段：遍历所有节点，尝试把每个节点挪到邻居社区里，看能不能让模块度变高。
- 聚合阶段：把第一阶段找到的社区压缩成超节点，构建一张新图。
然后在新图上重复这两步，直到模块度不再增长。整个过程就像滚雪球——小社区慢慢合并成大社区。
简单记忆法则：
- 第一阶段的输出：每个节点归属的社区ID
- 第二阶段的输出：社区级别的压缩图
- 第二阶段的结果，继续喂给第一阶段——往复循环
3.3 模块度增益计算——这个公式你得背下来
Louvain算法的核心决策依据，就是模块度增益。公式长这样：
ΔQ = [Σ_in + 2·k_i_in] / (2m) - [(Σ_tot + k_i) / (2m)]² - [Σ_in / (2m) - (Σ_tot / (2m))² - (k_i / (2m))²]别被这个公式吓到，我来拆解一下每个变量的含义：
| 符号 | 含义 |
|---|---|
| Σ_in | 目标社区内部的边权重之和 |
| Σ_tot | 目标社区所有节点连出的边权重之和（含外部） |
| k_i | 当前节点i的度（带权） |
| k_i_in | 节点i连向目标社区内部的边权重之和 |
| m | 全图总边权重 |
实际计算时，我们并不需要每次都算全量公式。我习惯把它简化为判断：
实际增量 = 把节点i加入社区C后的模块度 - 节点i单独成社区的模块度如果ΔQ > 0，就说明这一挪是划算的，应该执行。否则保持原状。
我的经验：很多初学者纠结于公式的每个符号，其实没必要。你只要记住——模块度增益衡量的是：把节点挪进去之后，社区内部连接密度是否比随机连接更“密”了。这个直觉比公式本身更重要。
3.4 两阶段迭代的伪代码
这个算法的实现逻辑其实挺简洁的：
输入：图 G = (V, E)，权重矩阵 w
输出：社区划分 C
初始化：每个节点自己是一个社区
repeat
// 第一阶段：局部移动
for each node i in V:
记录当前社区 c_old = C[i]
找出使ΔQ最大的邻居社区 c_best
if ΔQ(c_best) > 0:
C[i] = c_best
// 第二阶段：聚合
构建新图 G'：
原图在同一个社区内的节点 → 压缩为一个超节点
超节点间的边权重 = 原社区间所有跨边权重之和
令 G = G'
until 模块度不再增长
return C这里有个细节要注意：第一阶段不是一次性遍历完所有节点就结束，而是重复遍历直到没有节点愿意挪窝为止。我在项目里实测过，通常3-5轮遍历后就会收敛。
3.5 模块度调整的避坑指南
我曾经踩过的坑：
有一回做学术合作网络分析，跑Louvain算法死活得不到理想的社区结构。查了两天才发现——问题出在边权归一化上。原始数据里有些作者合作论文数上千篇，而大部分只有个位数，不归一化的话，模块度计算会被极少数超大权重带偏。
经验教训：强烈建议在运行Louvain之前，先对边权重做一次log变换或阈值裁剪。否则算法会把所有节点吸到那几个权重高的“明星节点”周围，社区结构全被抹平了。
3.6 Louvain算法的已知缺陷
虽然Louvain很好用，但它不是完美的。我总结了几点：
- 分辨率极限：小社区容易被吞掉，因为模块度本身偏向于生成大社区
- 连接分辨不清：一个节点和两个社区连接强度差不多时，算法可能会随机选一个
- 聚合阶段的缺陷：把社区内的内部结构全部抹掉了，导致后续迭代精度下降
正是这些缺陷，催生了下文要讲的Leiden算法。你可以把Leiden理解为：在Louvain的基础上，加了一个“局部细化”的阶段，专门修复聚合阶段丢掉细节的问题。
好，我们来整理一下Louvain算法整个流程的核心逻辑：
这张图已经很清晰了：每一次外层迭代，都是先做节点级别的精细调整，再做社区级别的粗粒化压缩。直到某次迭代结束后，整个图的模块度不再上升，算法就终止了。
3.7 模块度计算的实际代码
给个Python版本的模块度计算实现，方便你对照理解：
def modularity(G, community_of):
"""计算给定社区划分的模块度"""
m = G.size(weight='weight') # 总边权重
total = 0.0
for community in set(community_of.values()):
nodes_in_c = [n for n in G if community_of[n] == community]
subG = G.subgraph(nodes_in_c)
l_c = subG.size(weight='weight') # C社区内部边权重和
# 社区内节点度之和（带权）
d_c = sum(d for _, d in G.degree(nodes_in_c, weight='weight'))
total += (l_c / m) - (d_c / (2 * m)) ** 2
return total这段代码虽然简单，但跑几百万节点的图时要小心——vectorized版本比纯循环快两个数量级。我后来改用numpy批量计算社区度再求和，内存占用也降了不少。
核心提醒：Louvain算法的模块度增益，本质上是社区内实际连边密度与随机图下期望连边密度的差值。你理解了这句话，就理解了Louvain算法的全部。
3.8 小结
回顾一下，我们搞定了三件事：
- 两阶段迭代：局部移动 + 聚合，交替推进
- 模块度增益：判断每次节点迁移是否划算的数学标尺
- 算法终止条件：模块度不再增长