经典论文难度：入门

社会网络与生物网络中的社团结构

Community structure in social and biological networks

Girvan M, Newman MEJ · PNAS 2002 · DOI: 10.1073/pnas.122653799

社团结构边介数分裂式算法空手道俱乐部食物网

一句话

提出按边介数反复删边的分裂式社团发现算法，在人工网络、空手道俱乐部和食物网等数据上找到了有意义的社团。

相关专题：社团结构与社区发现、网络分析流程与 NetworkX 实践

VIDEO讲解视频

社会网络与生物网络中的社团结构4 分 41 秒

文字稿

大家好，这一期我们精读 Girvan 和 Newman 2002年发表在PNAS上的论文。它提出了按边介数反复删边的社团发现算法。

当时的网络研究集中在小世界、幂律和聚集系数，作者指出还有一个普遍但被忽视的性质，叫社团结构。社交网络中的兴趣群体、引文网络中的研究方向、代谢网络中的功能模块，都属于这一类。标准的层次聚类从最相似的节点对开始合并，只有一条边的边缘节点常被孤立出来。作者把思路倒过来，不去找社团的核心，而是找社团之间的边界，再逐步删掉它们。

关键概念是边介数，它是所有节点对之间的最短路径中，经过某条边的路径数目。如果一对节点之间有多条最短路径，就按等权分摊，使这对节点的总权重为1。它是 Freeman 节点介数在边上的推广。社团之间只靠少数几条边相连，跨社团的最短路径都要挤过这些边，所以它们的边介数很高。

边介数建立在最短路径之上，先要求出节点之间的最短路径。画面中从红圈节点出发做广度优先搜索，数字是它到各节点的距离。从每个节点出发都做一次搜索，就能累计出每条边被多少条最短路径经过。用 Newman 的快速算法，算一次全部边介数的时间与边数乘以节点数成正比。

算法只有四步，先计算所有边的边介数，删掉最大的那条。然后重新计算受影响的边的边介数，再删掉最大的，直到没有边剩下。画面是 Zachary 空手道俱乐部网络，红色粗线是下一条将被删除的边。删边过程中网络逐步分裂，不同颜色代表分出的社团，记录分裂顺序就得到一棵层次树。右边的模块度是2004年的后续论文才提出的指标，原文中还没有它。

如果两个社团之间有多条边，最短路径会分散在这些边上。一次性计算边介数，只能保证其中至少一条很高，其余的可能并不高。每删一条就重算，才能保证剩下的社团间边总有一条突显出来，这一步至关重要。

人工网络有128个节点、4个社团，每个节点的社团间连边不超过6条时，几乎全部归类正确。空手道俱乐部的34名成员后来分裂为两派，算法第一次分裂只分错了3号节点。在2000赛季美国大学橄榄球赛程网络上，找到的社团与联盟划分高度吻合。圣塔菲研究所合作网的社团主要沿学科划分，也有社团是按方法相似形成的。切萨皮克湾食物网分出两个社团，大体对应浮游和底栖生物，每个社团都包含多个营养级。

本文只给出完整的层次树，没有切在哪一层的客观标准，两年后模块度补上了这一点。算法在稀疏图上约为节点数的三次方，太慢，后来出现了谱方法和 Louvain 等快速算法。2007年有研究指出，模块度存在分辨率极限，可能把小社团合并。稠密网络上算法可能表现不佳，后来的重叠社团和随机块模型也拓展了社团的定义。

食物网的结果说明，社团可以按栖息地形成，而不同于传统的按营养级聚类。生物网络中的功能模块和疾病模块，都依赖社团发现方法。对脑功能网络这类加权网络，还要想清楚权重应当解释为距离还是强度。

总结一下，社团之间的少数边承载了大量最短路径，边介数很高。反复删除边介数最大的边，并且每次重算，网络就会沿社团边界一层层裂开。记录分裂顺序得到层次树，在人工网络、空手道俱乐部和食物网上都找到了有意义的社团。何时停止切分和计算太慢这两个问题，催生了模块度和后来的快速算法。可以用 NetworkX 自带的 Girvan Newman 函数，亲手复现空手道俱乐部的结果。

一句话看懂

社团之间只靠少数几条边相连，所有跨社团的最短路径都要挤过这几条边，因此它们的“边介数”很高。反复删除边介数最大的边（每删一次重新计算），网络就会沿社团边界一层层裂开。

研究背景与问题

1998–2001 年间，网络研究集中于小世界性、幂律度分布和聚集系数。作者指出还有一个普遍但被忽视的性质：社团结构——节点分成若干组，组内连接紧密、组间连接稀疏。社交网络中的兴趣群体、引文网络中的研究方向、代谢网络中的功能模块都属于此类。

当时的标准方法是社会学中的层次聚类：给每对节点定义相似度，从最相似的节点对开始逐步合并。作者指出这种“凝聚式”方法有一个毛病：边缘节点（只有一条边连向网络的节点）与谁都不太相似，常被孤立出来，而直观上它们显然属于所连的那个社团。

核心思想与方法

作者把思路倒过来：不去找社团的“核心”，而是找社团之间的“边界”，并逐步删掉它们。

边介数（edge betweenness）：网络中所有节点对之间的最短路径中，经过某条边的路径数目。若一对节点之间有多条最短路径，每条按等权分摊，使该节点对的总权重为 1。它是 Freeman 节点介数在边上的推广。

算法只有四步：

计算所有边的边介数；
删除边介数最大的边；
重新计算受删除影响的边的边介数；
回到第 2 步，直到没有边剩下。

删边过程中网络逐步分裂，记录分裂顺序即得到一棵层次树（树状图）。第 3 步的“重新计算”至关重要：如果两个社团之间有多条边，一次性计算只能保证其中至少一条边介数高，其余可能不高；每删一条就重算，才能保证剩余的社团间边总有一条突显出来。

计算量方面，用 Newman 的快速算法计算一次全部边介数需要 $O(mn)$ 时间（ $m$ 条边、 $n$ 个节点），整个算法最坏为 $O(m^2n)$ ，稀疏图上约为 $O(n^3)$ 。

主要发现

人工网络：128 个节点、每个节点度为 16、分为 4 个社团，改变每个节点连向其他社团的边数 $z_{\text{out}}$ 。 $z_{\text{out}}\le6$ 时几乎 100% 的节点被正确归类；直到每个节点的社团间连接接近社团内连接时，正确率才开始下降。
Zachary 空手道俱乐部（34 名成员，后因管理者与教练的矛盾分裂为两派）：算法的第一次分裂与实际的两派几乎完全一致，只有 3 号节点被分错。
美国大学橄榄球赛程网络（2000 赛季）：球队按“联盟”组织，联盟内比赛多于联盟间比赛；算法找到的社团与联盟划分高度吻合。
圣塔菲研究所合作网：271 名科学家，最大分支 118 人。社团主要沿学科划分（统计物理、数学生态学、RNA 结构、基于主体的经济与交通模型），后者说明社团也可以按“方法相似”而非“课题相同”形成。
切萨皮克湾食物网（33 个主要类群，忽略方向）：分出两个大小相近的社团，大体对应浮游（中上层）和底栖生物，每个社团都包含多个营养级——这与按营养级聚类的传统方法不同，也是标题中“生物网络”的来源。

怎样读这篇论文

先读第 2 节对层次聚类的批评，理解为什么要从“边界”而不是“核心”入手；然后精读算法四步及“为什么要重算”那一段；接下来按图 3（人工网络正确率）、图 4（空手道俱乐部的网络和树状图）读测试部分。合作网和食物网两个应用可以挑一个细读。结论中关于加权、有向推广和速度改进的展望值得注意，它们几乎都在后来实现了。

局限与后续工作

何时停止切分：本文只给出完整的层次树，没有给出“切在哪一层”的客观标准，作者依靠已知结构或直观判断。两年后 Newman 与 Girvan（2004）提出模块度 $Q$ 来选择最佳划分，模块度从此成为社团发现的核心指标。
计算太慢： $O(n^3)$ 的复杂度使它无法用于大网络。后续出现了贪心模块度优化、谱方法和 Louvain 算法（Blondel 等 2008）等快速方法。
模块度自身的局限：Fortunato 与 Barthélemy（2007）指出模块度存在分辨率极限，可能把小社团合并；模块度最大化的解往往有大量近似最优的退化解。
稠密网络：作者已注意到有些食物网是稠密的，算法表现可能不佳。
更一般的社团概念：重叠社团、层次社团、随机块模型等统计推断方法拓展了“社团”的定义。

关联知识

Girvan–Newman 算法与边介数直接讲解本文方法，社团结构与社区发现中的空手道俱乐部交互演示可以自己尝试分组并观察模块度变化。注意该专题中“模块度在 5 个社团时最大”等结论来自 2004 年的后续论文，而非本文。
NetworkX 中的 girvan_newman 函数就是本文算法（见NetworkX 速查表），可以用它复现图 4。
生物网络中的功能模块和疾病模块（人类疾病网络与疾病模块、疾病模块：定义与检测）都依赖社团发现方法。

延伸思考

边介数依赖最短路径。对加权网络（例如脑功能网络），你会如何定义边介数？权重应当解释为“距离”还是“强度”？
空手道俱乐部中 3 号节点被分错。请查看这个节点的连接，解释为什么从拓扑上看它“两边都像”。
食物网中算法按栖息地而非营养级划分社团。这说明社团结构反映的是哪一类关系？如果把边的方向考虑进来，结论可能会怎样改变？