生物医学网络科学Biomedical Network Science
经典论文难度：入门

大规模网络中社团的快速展开

Fast unfolding of communities in large networks

Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E · Journal of Statistical Mechanics 2008 · DOI: 10.1088/1742-5468/2008/10/P10008

Louvain 算法模块度优化层次社团大规模网络贪心算法

一句话

提出“局部移动 + 聚合”反复迭代的模块度优化算法（Louvain），在上亿节点的网络上几小时内完成社团发现。

相关专题：社团结构与社区发现

一句话看懂

先让每个节点单独成为一个社团，让每个节点尝试搬到邻居所在的社团、只要模块度增加就搬；搬不动了，就把每个社团缩成一个“超级节点”，在新网络上重复。这个简单的两阶段循环就是今天最常用的社团发现算法之一，Louvain 算法。

研究背景与问题

模块度最大化是社团发现的主流思路，但精确求解是计算上困难的问题，只能用近似算法。到 2008 年，最快的方法是 Clauset、Newman 与 Moore（CNM）的贪心合并算法，但它得到的模块度往往明显低于模拟退火，还倾向于产生吞并大部分节点的“超级社团”，难以处理百万节点以上的网络。文献中处理过的最大网络约 550 万节点。

与此同时，手机通话记录、网页链接等数据已经达到数千万乃至上亿节点。作者要解决的是：能否设计一个既快、模块度又高，并能给出层次结构的算法？

核心思想与方法

算法对加权网络定义，无权网络可视为权重全为 1。

第一阶段：局部移动。 初始时每个节点自成一个社团。依次考察每个节点 ii：计算把 ii 从当前社团移出、放入某个邻居 jj 所在社团时模块度的变化，选增益最大的社团，若增益为正就移动，否则留在原处。反复扫描所有节点，直到没有任何单个移动能提高模块度。

第二阶段：聚合。 把第一阶段得到的每个社团缩成一个新节点；两个新节点之间的边权为原社团之间所有边权之和，社团内部的边变成新节点的自环。

一次“局部移动 + 聚合”称为一轮（pass）。在新网络上重复，直到模块度不再增加。

移动增益：把孤立节点 ii 放入社团 CC 的模块度变化

ΔQ=[Σin+ki,in2m−(Σtot+ki2m)2]−[Σin2m−(Σtot2m)2−(ki2m)2]\Delta Q=\Big[\frac{\Sigma_{in}+k_{i,in}}{2m}-\Big(\frac{\Sigma_{tot}+k_i}{2m}\Big)^2\Big]-\Big[\frac{\Sigma_{in}}{2m}-\Big(\frac{\Sigma_{tot}}{2m}\Big)^2-\Big(\frac{k_i}{2m}\Big)^2\Big]

其中 Σin\Sigma_{in} 是 CC 内部边权之和，Σtot\Sigma_{tot} 是与 CC 中节点相连的边权之和，kik_i 是节点 ii 的强度，ki,ink_{i,in} 是 ii 连向 CC 的边权之和，mm 是全网边权之和。

速度来自两点：ΔQ\Delta Q 只需要局部量，计算极快；社团数在前几轮急剧减少，大部分时间花在第一轮。每一轮的结果构成层次结构中的一层，算法天然给出“社团的社团”。

主要发现

  1. 速度与质量（表 1）：在 34 节点到 1.18 亿节点的一系列网络上与 CNM、Pons–Latapy、Wakita–Tsurumi 三种方法比较，本文方法在每个网络上的模块度都不低于其他方法，速度也最快。例如在 32.5 万节点的 nd.edu 网页网络上，模块度 0.935，用时 3 秒；CNM 为 0.927，用时 5034 秒。
  2. 超大网络：在 3900 万节点、7.83 亿条边的 .uk 网页网络上用时 12 分钟；在 1.18 亿节点、约 10 亿条边的 WebBase 网页网络上用时 152 分钟。作者指出，限制规模的是内存而不是计算时间。
  3. 轮数很少：空手道俱乐部只需 3 轮（34 个节点先分成 6 个社团，再并成 4 个，第三轮没有变化），文中所有例子都少于 5 轮。
  4. 比利时手机网络（260 万用户，边权为 6 个月内的通话次数）：得到 6 层层次结构；顶层有 261 个超过 100 人的社团，约覆盖 75% 的用户。在 36 个超过 1 万人的社团中，除一个位于法语区与荷兰语区交界处的社团外，其余社团中都有超过 85% 的成员说同一种语言。
  5. 人工基准网络：在 128 个节点、4 个社团的标准基准上，准确率与 Pons–Latapy 等算法相当；作者承认 Duch–Arenas 极值优化和模拟退火更准确，但它们计算代价太大，只能用于小得多的网络。

怎样读这篇论文

论文只有 12 页。先看图 1（两阶段示意图），再读第 2 节方法和 ΔQ\Delta Q 公式，自己在纸上对一个 6 个节点的小网络手算一轮。然后看表 1 和第 3 节手机网络的例子（图 3、图 4）。关于分辨率极限的讨论（图 2，30 个团组成的环）值得细读，因为作者的观点后来被证明需要修正。

局限与后续工作

  • 分辨率极限并未真正解决：作者认为，由于第一阶段只移动单个节点，小社团不易被错误合并，中间层次的划分也有意义（图 2 中第一轮正确分出了 30 个团，第二轮才两两合并）。但最终输出仍是模块度的局部最大值，分辨率极限依然存在；实践中常用带分辨率参数 γ\gamma 的模块度来调整社团大小。
  • 节点顺序与随机性：作者指出结果依赖节点的访问顺序，并认为它对最终模块度影响不大，但会影响速度。实践中不同随机种子可能给出不同的划分，应报告多次运行的稳定性。
  • 内部不连通的社团：Traag、Waltman 与 van Eck（2019）发现，Louvain 可能产生内部不连通甚至连接很差的社团，并提出了加入“细化”步骤的 Leiden 算法，现在一般推荐优先使用 Leiden。
  • 贪心的本质：作为局部优化，算法没有最优性保证，在没有社团结构的随机网络中也会返回相当高的模块度。

关联知识

延伸思考

  1. 为什么社团数在前几轮急剧减少，就意味着算法的大部分时间花在第一轮？试用每轮网络规模的变化估计总计算量。
  2. 手机网络中“交界社团”的语言构成比较均衡。如果把这个思路用到医院患者转诊网络或细胞间相互作用网络上，“交界社团”可能代表什么？
  3. 在实际分析中，Louvain 每次运行可能给出不同的划分。请设计一个方案来报告社团划分的稳定性，并说明你会用什么指标比较两次划分的相似程度。