Girvan–Newman 算法与边介数

边介数

社团之间的连边少，所以社团之间的最短路径必须挤过这些少数“桥”。这启发了边介数（edge betweenness）的定义：

社团之间的边介数高，社团内部的边介数低。这与 Granovetter 的“弱关系是桥”一脉相承。

算法步骤

1. 计算所有边的边介数；
2. 删除边介数最大的边；
3. 重新计算剩余所有边的边介数（删边会改变最短路径，这一步不能省略）；
4. 重复第 2–3 步，直到所有边都被删除。

在删边过程中，网络逐渐分裂为越来越多的连通分支，这一过程形成一棵树状图（dendrogram）。在哪一层“切”下去？常用做法是选择模块度最大的那一层。

在空手道俱乐部网络上，Girvan–Newman 算法的第一次分裂与真实的两派分裂几乎一致，只有个别节点被分到另一侧；继续分裂，模块度在 5 个社团时达到最大（约 0.40）。

分裂式与凝聚式

Girvan–Newman 是分裂式（divisive）层次方法：从整个网络出发，逐步删去“最不像社团内部”的边。与之相对的凝聚式（agglomerative）方法从单个节点出发逐步合并最相似者，见层次聚类。删边的依据也不限于边介数：Radicchi 等（2004）用边聚集系数（一条边参与的三角形数相对于可能的最大数）作为局部替代量——社团之间的边很少处在三角形中——计算量远小于边介数。

优缺点

优点：思路直观，输出完整的层次结构。缺点：每删一条边都要重新计算所有边介数，单次计算需要 $O(mn)$，总计算量约为 $O(m^2 n)$，只适用于几百到几千个节点的网络。