Louvain 与 Leiden 算法

Louvain 算法

Louvain 算法（Blondel 等，2008）是目前最常用的社团发现算法之一，它反复执行两个阶段：

1. 局部移动：开始时每个节点自成一个社团。依次考察每个节点，把它移到能使 $Q$ 增加最多的邻居社团中（若都不能增加则不动），直到没有节点再移动；
2. 聚合：把每个社团压缩成一个“超节点”，社团内部的边变成超节点的自环，社团之间的边合并为加权边。在新网络上回到第 1 步。

每一轮聚合得到一层更粗的划分，自然形成层次结构。Louvain 速度很快，可处理数百万节点的网络。局部移动中 $\Delta Q$ 的计算公式与伪代码见数学推导与算法。

Louvain 的缺陷：连接不良的社团

Traag、Waltman 与 van Eck（2019）指出 Louvain 有一个长期被忽视的问题：它可能产生连接不良（badly connected）甚至内部不连通的社团。原因在于局部移动阶段：设节点 $v$ 是社团 $C$ 内部连接其他几部分的“桥”，当 $v$ 被移到另一个社团后，$C$ 剩下的部分可能已经断开，但它们之后作为一个整体被聚合成超节点，以后的层次中再也不会被拆开。作者在若干真实网络上的实验中观察到，Louvain 的结果中最多约 25% 的社团连接不良、最多约 16% 的社团不连通，而且迭代运行 Louvain 会让问题更严重。这直接违背了 H2（社团应当连通）。

Leiden 算法的改进

Leiden 算法在“局部移动”和“聚合”之间加入细化（refinement）阶段：

1. 快速局部移动：与 Louvain 相似，但只把“邻居发生变化”的节点放回待访问队列，而不是每轮遍历全部节点，因此更快；
2. 细化：在第 1 步得到的每个社团 $C$ 内部，从单点出发重新合并，只允许把节点并入与它连接足够好的子社团，并且合并时带有一定随机性（由参数 $\theta$ 控制）；这样得到的细化划分中，每个子社团都是 $C$ 的连通子集；
3. 聚合：以细化后的子社团为超节点构造聚合网络，但用第 1 步的划分作为聚合网络的初始划分。

由于聚合基于细化划分，一个原来连接不良的社团在下一层会以多个超节点的形式出现，仍然可以被拆开。作者证明：Leiden 每次迭代后的社团都是连通的（进一步满足 $\gamma$-连接性）；反复迭代直到划分不再改变时，所有社团的所有子集都处于局部最优位置。实践中 Leiden 通常更快，且得到的 $Q$ 与 Louvain 相当或更高。

质量函数的选择：模块度与常数 Potts 模型

Louvain/Leiden 只是优化框架，可以优化不同的质量函数。Traag、Van Dooren 与 Nesterov（2011）提出常数 Potts 模型（constant Potts model, CPM）： $$H_{\text{CPM}}=\sum_c\left[e_c-\gamma\binom{n_c}{2}\right],$$ $e_c$ 为社团内部的边数（或边权之和），$n_c$ 为社团节点数。其含义是：社团内部的边密度应高于 $\gamma$，社团之间的边密度应低于 $\gamma$。由于 CPM 中没有全网边数 $m$，它是无分辨率极限的：一个子图是否被识别为社团只取决于其自身与相邻部分，而不取决于网络其余部分有多大。代价是 $\gamma$ 的取值有了“密度”的绝对含义，需要按网络的边密度量级来选。在由 $K_5$ 团组成的环上，模块度在团数超过 22 时开始合并相邻团，而 CPM（取 $0<\gamma<$ 团内密度）不论团数多少都把每个团单独识别出来（代码示例）。