经典论文难度：进阶

网络中的模块度与社团结构

Modularity and community structure in networks

Newman MEJ · PNAS 2006 · DOI: 10.1073/pnas.0601602103

模块度模块度矩阵谱方法主特征向量社团发现不可分子图

一句话

把模块度写成模块度矩阵的二次型，按其主特征向量的正负号二分网络，得到快速而高质量的社团发现算法。

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

VIDEO讲解视频

网络中的模块度与社团结构5 分 5 秒

文字稿

大家好，这一期我们精读2006年发表在PNAS上的模块度谱方法论文。全文只有6页，推导简洁，是理解社团发现中谱方法最好的入口。

寻找社团有两条传统，计算机科学里的图划分，通常事先知道要分几组、每组多大。社会学和物理学里的社团发现，组数和大小都未知，网络甚至可能没有好的划分。如果只最小化组间边数又不限制组的大小，最优解永远是全部放在一组。模块度解决了这个问题，好的划分不是组间边少，而是组间边比随机期望少。用模拟退火最大化模块度效果很好，但对大网络太慢，本文要找既快又好的方法。

模块度矩阵等于实际连边，减去保持度的随机网络中的期望边数。二分时给每个节点一个正1或负1的标签，模块度就写成标签向量的二次型。如果标签可以取任意实数，最优解就是平行于最大特征值对应的主特征向量。但标签只能取正负1，于是按主特征向量各分量的正负号来分组。模块度矩阵每行每列之和为零，所以全1向量总是它特征值为零的特征向量。

这个方法有三个好性质，第一，不需要预设组的大小。第二，它会拒绝划分，如果没有正特征值，所有节点都留在一组，网络是不可分的。作者据此把社团定义为不可分的子图，这是全文最有思想深度的地方。第三，分量绝对值大的节点对模块度贡献大，接近零的节点处在两个社团的边界上。

要得到多于两个社团，就反复二分。关键细节是，不能删掉组间边后直接对子图重算。那样度会改变，优化的就不再是原网络的模块度，正确做法是使用广义模块度矩阵。当某次划分对模块度的贡献不为正时，就停止划分。最后再逐个移动节点做微调，让模块度再提高几个百分点。作者说正是这几个百分点，让方法从好变成了优秀。

画面上是空手道俱乐部网络，这里演示的是作为对照的Girvan Newman算法。它反复删除边介数最大的边，也就是社团之间的桥，右边记录模块度的变化。而本文的谱方法只做一次二分，结果就与俱乐部实际分裂成的两派完全一致。主特征向量中权重最大的几个节点，正好对应两派的核心人物。

在六个网络上，本文方法的模块度都高于Girvan Newman算法和贪心算法。以约2.7万节点的凝聚态物理合作网络为例，贪心算法的模块度是0.668。极值优化是0.679，本文方法达到0.723。在105本政治书籍的共购网络里，找到4个社团，自由派和保守派各自聚成一团。1225个政治博客恰好分成两团，一组97%是保守派，另一组93%是自由派。最大的合作网络，在当时的个人计算机上约20分钟就能完成。

模块度本身有分辨率极限，大网络中较小的社团可能被合并，即使它们是明显的团块。模块度地形上还有大量接近最优的高原，不同划分得分相近，结构却差别很大。没有社团结构的随机图，最大模块度也可能明显大于零，高模块度本身不是证据。规模上，两年后的Louvain算法把网络推到了上亿节点。随机块模型等统计推断方法，能做模型选择，并给出不确定性。

在生物网络中，算法能否拒绝划分尤其重要，否则在无结构的数据里也会找到社团。基因共表达网络中，不可分子图可能很大，要结合分辨率极限检查其中的子模块。蛋白相互作用网络里处在社团边界上的蛋白，对应什么功能角色，也值得思考。

总结一下，模块度可以写成模块度矩阵的二次型。按主特征向量的正负号二分，得到了又快又好的社团发现算法。如果模块度矩阵没有正特征值，算法会告诉你网络不该再分。但模块度有分辨率极限，高模块度本身也不能证明存在社团。建议先自己补上从模块度定义到二次型的那一步代数，再读不可分的讨论。

一句话看懂

模块度可以写成 $Q\propto\mathbf s^\top B\mathbf s$ ，其中 $B$ 是“实际连边减去随机期望”的模块度矩阵。于是“找最好的二分”近似为“找 $B$ 的最大特征值对应的特征向量，按分量正负分组”。如果 $B$ 没有正特征值，算法会告诉你：这个网络不该再分。

研究背景与问题

寻找网络中的社团有两条传统：计算机科学中的图划分（graph partitioning），通常事先知道要分几组、每组多大，目标是让组间边最少；社会学和物理学中的社团发现，组数和大小都未知，而且网络可能根本没有好的划分。

如果直接最小化组间边数又不限制组的大小，最优解永远是“全部放在一组”。Newman 与 Girvan（2004）提出的模块度解决了这个问题：好的划分不是组间边少，而是组间边比随机期望少。用模拟退火最大化模块度效果很好，但对大网络太慢。本文要回答：能否找到既快又好的模块度优化方法？

核心思想与方法

设网络有 $n$ 个节点、 $m$ 条边，节点 $i$ 的度为 $k_i$ 。在保持度的随机网络中， $i$ 与 $j$ 之间的期望边数是 $k_ik_j/2m$ 。对二分，令 $s_i=\pm1$ 表示节点属于哪一组。

模块度矩阵： $B_{ij}=A_{ij}-\dfrac{k_ik_j}{2m}$ 。它是实对称矩阵，每行每列之和为零，因此 $(1,1,\dots,1)$ 总是它特征值为 0 的特征向量。

模块度的二次型： $Q=\dfrac{1}{4m}\sum_{ij}B_{ij}s_is_j=\dfrac{1}{4m}\mathbf s^\top B\mathbf s$ 。

把 $\mathbf s$ 展开为 $B$ 的特征向量的线性组合， $Q$ 正比于 $\sum_i(\mathbf u_i^\top\mathbf s)^2\beta_i$ ， $\beta_i$ 是特征值。若 $\mathbf s$ 可以取任意实向量，最优解就是让它平行于主特征向量 $\mathbf u_1$ 。但 $s_i$ 只能取 $\pm1$ ，作者采用与谱划分相同的近似：按 $\mathbf u_1$ 各分量的正负号分组。

这个方法有三个好的性质：

不需要预设组的大小；
会拒绝划分：若 $B$ 没有正特征值，主特征向量就是全 1 向量，算法把所有节点留在一组。作者称这样的网络为“不可分的”（indivisible），并把社团定义为不可分的子图；
分量的大小有意义：分量绝对值大的节点对 $Q$ 贡献大，接近 0 的节点处在两个社团的边界上。

多于两个社团：反复二分。关键细节是不能简单删掉组间边后对子图重算，因为那样度会改变，优化的就不是原网络的模块度。正确做法是对子图 $g$ 使用广义模块度矩阵 $B^{(g)}_{ij}=B_{ij}-\delta_{ij}\sum_{l\in g}B_{il}$ ，当某次划分对 $Q$ 的贡献不为正时停止。

微调：谱二分之后，再用类似 Kernighan–Lin 的方法逐个移动节点，使 $Q$ 进一步增大。作者报告这一步通常只让 $Q$ 再提高几个百分点，但正是这几个百分点让方法从“好”变成“优秀”。

主要发现

空手道俱乐部：一次二分的结果与俱乐部实际分裂的两派完全一致；主特征向量中权重最大的几个节点对应两派的核心人物。
与其他算法比较（表 1，六个网络）：本文方法得到的模块度在所有网络上都高于 Girvan–Newman 算法和 Clauset–Newman–Moore 贪心算法；与 Duch–Arenas 极值优化相比，千个节点以下的网络上相差不到千分之几，在更大的网络上更好。例如在约 2.7 万节点的凝聚态物理合作网络上，三种方法的 $Q$ 分别为 0.668（贪心）、0.679（极值优化）和 0.723（本文）。
政治书籍共购网络（105 本书）：找到 4 个社团，其中一个几乎全是自由派书籍，一个几乎全是保守派，中间派书籍大多落在另外两个社团中。
政治博客网络（1225 个博客）：最优划分恰好是两个社团，一个 638 个节点中 97% 是保守派，另一个 587 个节点中 93% 是自由派，且两组都不可再分。
速度：稀疏网络上运行时间约为 $O(n^2\log n)$ ，最大的合作网络在当时的个人计算机上约 20 分钟完成。

怎样读这篇论文

全文只有 6 页，推导简洁，是理解“谱方法”最好的入口。建议先读式 (1)–(3)，自己补上从 $Q$ 的定义到二次型的一步代数；然后读“不可分”的讨论，这是本文最有思想深度的部分；再看图 2（空手道俱乐部，节点灰度表示特征向量分量）和表 1。关于复杂度的段落可以快速读过。

局限与后续工作

模块度本身的问题：Fortunato 与 Barthélemy（2007）证明了模块度的分辨率极限：在大网络中，规模小于约 $\sqrt{2m}$ 量级的社团可能被合并，即使它们是明显的团块。Good 等（2010）进一步发现，模块度的地形有大量接近最优的“高原”，不同划分的 $Q$ 相差无几但结构差别很大。
随机网络也有高模块度：没有任何社团结构的随机图，其最大模块度也可能明显大于零，所以“ $Q$ 较大”本身不能证明网络有社团。
规模： $O(n^2\log n)$ 对百万级网络仍然太慢。两年后的 Louvain 算法把规模推到了上亿节点。
从优化到推断：随机块模型（Karrer 与 Newman 2011）等统计推断方法可以做模型选择、给出不确定性，并避免在无结构的网络中“找到”社团。Newman（2016）还证明了模块度最大化与某种随机块模型的极大似然等价。

关联知识

谱方法与层次聚类和数学推导与算法中“从模块度到谱二分”完整推导了本文的方法，包括 $\mathbf s^\top B\mathbf s$ 的展开、放松与取整、子图的广义模块度矩阵；模块度一节和推导部分讨论了分辨率极限。
本文对“不可分”的处理，可以和社团结果的验证与解读对照：算法是否应该允许“不分”，在生物网络中尤其重要。

延伸思考

证明模块度矩阵每行之和为零。由此说明：为什么只要 $B$ 有正特征值，主特征向量就一定同时含有正分量和负分量？
本文把社团定义为“不可分的子图”。在一个基因共表达网络中，这个定义得到的社团可能很大。结合分辨率极限，你会怎样检查一个大社团是否还包含有生物学意义的子模块？
主特征向量分量接近 0 的节点处在两个社团的边界上。在蛋白质相互作用网络中，这类“边界蛋白”可能对应什么样的功能角色？