生物医学网络科学Biomedical Network Science
社团结构与社区发现03 / 19

模块度

阅读
约 3 分钟

思路：与随机期望比较

一个好的划分，社团内部的边应当“多于随机情况下的预期”。问题是：随机预期应该怎么算？如果只按边数平均分配，枢纽节点因为连接多，会被误认为与谁都“紧密”。Newman 和 Girvan 选用的零模型是配置模型（configuration model）：保持每个节点的度不变，随机重新配对所有“半边”。在这个零模型下，度为 kik_i 和 kjk_j 的两个节点之间期望的边数为 kikj2m\dfrac{k_i k_j}{2m}（mm 为总边数）。

模块度（modularity）： Q=12m∑i,j[Aij−kikj2m]δ(ci,cj),Q = \frac{1}{2m}\sum_{i,j}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j), 其中 cic_i 是节点 ii 所属的社团，δ(ci,cj)=1\delta(c_i,c_j)=1 当且仅当 i,ji,j 属于同一社团。等价地按社团求和： Q=∑c[lcm−(dc2m)2],Q = \sum_{c}\left[\frac{l_c}{m} - \left(\frac{d_c}{2m}\right)^2\right], lcl_c 为社团 cc 内部的边数，dcd_c 为社团 cc 内所有节点的度之和。

第二种写法的含义很直观：lc/ml_c/m 是“实际落在社团内部的边的比例”，(dc/2m)2(d_c/2m)^2 是“随机配对时预期落在社团内部的比例”。本专题页面的模块度演示可以点击节点改变分组，实时观察 QQ 的变化。

一个手算例子

两个三角形 {1,2,3} 与 {4,5,6}，再用一条边 3–4 相连。共 m=7m = 7 条边。

  • 划分为两个三角形：每个社团 lc=3l_c = 3；度为 2、2、3，dc=7d_c = 7。 Q=2×[37−(714)2]=2×(0.429−0.25)≈0.357Q = 2 \times \left[\dfrac{3}{7} - \left(\dfrac{7}{14}\right)^2\right] = 2 \times (0.429 - 0.25) \approx 0.357。
  • 所有节点放在一个社团：Q=77−12=0Q = \dfrac{7}{7} - 1^2 = 0。
  • 每个节点单独一个社团：没有内部边，Q=−∑i(ki/2m)2<0Q = -\sum_i (k_i/2m)^2 < 0。

加权与有向网络的推广

  • 加权网络：把 AijA_{ij} 换成边权 wijw_{ij}，kik_i 换成节点强度 si=∑jwijs_i=\sum_j w_{ij}，mm 换成总权重的一半。
  • 有向网络（Leicht 与 Newman 2008）：零模型改为“jj 的出度与 ii 的入度相乘”，Q=1m∑ij[Aij−kiinkjoutm]δ(ci,cj)Q=\frac{1}{m}\sum_{ij}\left[A_{ij}-\frac{k_i^{\text{in}}k_j^{\text{out}}}{m}\right]\delta(c_i,c_j)，mm 为有向边数。它只看边的密度，不看流动方向形成的循环；若社团的意义在于“信息在其中循环停留”，映射方程更合适。
  • 带符号网络（如含负相关的功能连接）：正、负边的零模型需要分别构造，不能直接把负权代入上式（见脑连接组中关于负相关的讨论）。

模块度的性质与局限

  • 取值范围：Q<1Q<1；整个网络作为一个社团时 Q=0Q=0。若划分含 ncn_c 个社团，则 Q≤1−1/ncQ\le1-1/n_c。实际网络中，“有明显社团结构”的划分通常 QQ 在 0.3–0.7 之间。
  • 随机网络也能得到不低的 QQ。在一个没有任何真实社团的 ER 网络上做模块度最大化，往往也能找到 QQ 达 0.3 以上的划分（Guimerà 等，2004），对稀疏的小网络尤其如此。因此 QQ 的绝对值不能直接说明“社团结构显著”，应与同样度序列的随机网络比较。这违背了 H3 的精神：模块度最大化本身无法区分“结构”与“涨落”。
  • 分辨率极限（resolution limit，Fortunato 与 Barthélemy，2007）：模块度的零模型依赖网络总边数 mm。在大网络中，度之和小于约 2m\sqrt{2m} 量级的社团，即使本身是完全连接的小团，也可能被合并到更大的社团中（推导见数学推导与算法）。
  • 简并性与模块度平台：Good、de Montjoye 与 Clauset（2010）发现，模块度函数在高值区不是一个尖峰，而是一片“高原”：存在数量随网络规模指数增长的划分，它们的 QQ 与最大值相差无几，但彼此结构差别很大。这解释了为什么各种启发式算法都能很快找到“高 QQ”划分，也意味着最大 QQ 的那个划分并没有特殊的可信度。

很多软件提供分辨率参数 γ\gamma（Reichardt 与 Bornholdt 2006）：Qγ=12m∑ij[Aij−γkikj2m]δ(ci,cj)Q_\gamma = \frac{1}{2m}\sum_{ij}[A_{ij} - \gamma\frac{k_ik_j}{2m}]\delta(c_i,c_j)。γ>1\gamma>1 得到更多、更小的社团，γ<1\gamma<1 得到更少、更大的社团。它不能消除分辨率问题，只是让你选择观察的尺度。报告结果时要写明 γ\gamma 的取值，最好展示结论在一系列 γ\gamma 下是否稳健（见多分辨率与共识聚类）。

贪心模块度算法

最早的快速模块度算法是 Newman（2004）的贪心凝聚法：开始时每个节点自成一个社团，每一步合并能使 QQ 增加最多（或减少最少）的一对相连社团，直到只剩一个社团，再选 QQ 最大的那一层。Clauset、Newman 与 Moore（2004）用堆结构把它加速到稀疏层次网络上约 O(nlog⁡2n)O(n\log^2 n)，常称 CNM 算法（NetworkX 中的 greedy_modularity_communities）。贪心合并倾向于先形成少数大社团、再吞并小社团，在基准测试中通常不如 Louvain 准确（见划分比较与基准检验）。

继续阅读