在社交网络分析里社区发现这个话题总结起来就是把一群看起来“抱团”的节点找出来。GN算法Girvan-Newman大概是这类算法里最常被拿来当入门教材的经典它用“边介数edge betweenness”作为标尺一层层剥掉网络里的“桥”让社区自己浮出来。但很多人在代码实现这一步卡住——GN慢慢在反复计算边介数而这背后的加速方案就是常说的fast betweenness算法Brandes算法。这篇文章我会把GN的完整实现思路、fast betweenness的加速原理以及一份可以直接跑起来验证的Python代码一起拆开讲适合正在啃社区发现代码、或者准备自己实现一遍经典图算法的朋友。1. 先搞清楚GN算法到底在求什么社区发现本质上是在回答一个问题一张图里哪些节点天然地聚成一团这个问题不像聚类那样有明确的特征向量图里只有节点和边所以我们只能靠结构信息来判断“抱团”。GN算法给出的答案是社区之间一定有“桥”把桥拆掉社区就出来了。1.1 边介数为什么会成为社区边界的最好裁判你可以把网络想象成一个小镇节点是住户边是道路。社区就是几个联系紧密的居民区。住在同一个居民区里的人来往频繁道路密集不同居民区之间只有少数几条主路相通。如果你想给小镇划分小区最朴素的做法就是找到那些“没有它就不方便串门”的关键道路——这就是边介数的直觉。边介数的正式定义是在一张无向图中对于任意两个节点 s 和 t它们之间有很多条最短路径如果其中某些最短路径经过了边 e那么边 e 就获得一次“贡献”。把所有节点对 s-t 的贡献加起来就得到这条边的介数。直观上介数越高的边越是连接两个区域的咽喉要道去掉它网络就会快速瓦解成两个相对独立的部分。需要注意的是边介数不是“边的度”那种局部指标。一条边的两个端点可能度数都不高但它依然可以是连接两个社区的唯一桥梁反过来社区内部的边即使两端度数很高因为它们的替代路径多介数反而不高。所以边介数天然地能区分“内部边”和“桥梁边”。1.2 从边介数到逐条删边GN的核心操作非常朴素甚至有点暴力计算当前图所有边的介数。找到介数最大的那条边把它删掉。重新计算剩余所有边的介数。重复第2步和第3步直到图里没有边可删。每删一条边这个图可能并不会立即分裂但当删除的边积累到一定程度图会“咔嚓”一声断成两个连通分量。这个“咔嚓”的位置就是一次有意义的社区划分。把所有分裂过程记录下来就形成了一棵层次分裂树也就是dendrogram。这里有个初学者容易误解的地方GN不是“算一次介数然后顺着排序从高到低一口气删完”。每删掉一条边之后剩余边的最短路径关系已经变了之前算出来的介数全部作废。所以主循环里必须每轮重新计算所有边介数。这也是GN复杂度高的重要原因后面我会专门算这笔账。1.3 完整迭代步骤和一个小例子我经常用一张最简单的手工图来理解GN两个五边形通过一条公共边相连。假设左边5个节点内部紧密相连右边5个节点内部也紧密相连中间的桥只有两条边。第一步桥边介数肯定最高先删掉其中一条此时图没断因为还有另一条桥第二步剩下那条桥的介数变成最高再删掉这时图分裂成两个连通分量社区划分完成。从这个例子你也可以看出一次删边未必立刻分裂但每删一条边图的连通性都在发生变化。实际写代码时我们不能只记录“图什么时候断”还应该把“每一步剩余的边集合”保存下来这样才能画出完整的层次结构。2. 关键加速点fast betweenness是如何把你从三层循环里捞出来的很多人误以为GN算法的瓶颈在“删边”本身其实不是。删边是O(1)的操作真正吃时间的是每轮都要重算一遍边介数。而fast betweenness算法也就是Brandes在2001年提出的介数中心性快速算法正是解决这个瓶颈的关键。2.1 朴素办法慢在哪如果按定义去算边介数流程是这样的枚举所有节点对 s-t对每一对节点求一次最短路径再统计哪些最短路径经过了哪些边。最直接的做法甚至可以写成三层循环外层枚举源节点中层枚举目标节点内层做BFS或者Dijkstra。这么做下来单次介数计算就是 O(n³) 的级别非常酸爽。更麻烦的是这种朴素实现里有很多重复劳动。每换一个源节点 s它到所有目标节点的最短路径树都要重新建一次但很多中间结果其实可以在同一棵BFS树里复用。GN算法要反复删边、反复计算介数如果介数计算本身就这么吃力整个算法就只能停留在玩具图上。2.2 Brandes算法的三个关键词BFS树、前驱、累积依赖Brandes算法的聪明之处在于对每一个源节点 s只做一次BFS同时把“从 s 到所有节点的最短路径条数”算出来然后把“所有经过某条边的最短路径贡献”在这一次BFS里累加到对应的边上。具体分两个阶段。第一个阶段还是BFS但是多维护两个东西。一是 sigma[v]表示从源节点 s 到 v 的最短路径条数二是前驱列表 predecessors[v]记录所有可能成为 v 在最短路径上一跳的邻居节点。BFS天然保证非负无权图的层次关系所以当遍历到邻居 w 时如果 dist[w] dist[v] 1说明 v 是 w 的最短路径前驱那么 sigma[w] 就累加上 sigma[v]。第二个阶段是反向累积。从BFS出队的顺序的逆序开始处理每个节点 w对于 w 的每个前驱 v计算一个“依赖值” contribution公式是contribution (sigma[v] / sigma[w]) * (1 delta[w])其中 delta[w] 是之前已经累积到的依赖值。这个值的含义是在所有从源点 s 出发、经过 w 的最短路径里那些通过 w 走向更远节点的路径对边 (v, w) 产生的介数贡献。把 contribution 累加到边 (v, w) 上同时累加到 delta[v] 上以便继续向前传播。这样就做到了一次BFS加上一次反向遍历就能把源节点 s 对所有边的介数贡献全部算完。所有源节点都走一遍边介数就齐了。单次介数计算复杂度从朴素写法的 O(n³) 直接降到 O(mn)在稀疏图上效果尤其明显。2.3 时间与空间复杂度到底怎么算我们来看GN的整体账。设图有 n 个节点、m 条边。Brandes算法计算全部边介数的时间是 O(mn)每次删边后都要重算一遍最多删 m 次所以GN的总复杂度是 O(m²n)。在稀疏图里 m 大约和 n 同阶总复杂度接近 O(n³)在稠密图里 m 接近 n²总复杂度会到 O(n⁵)确实疼。空间方面每一轮介数计算需要存邻接表、sigma、dist、predecessors、delta总空间是 O(mn)。如果网络规模在几千节点、上万边的量级单机Python实现还能撑得住到了百万级边GN就基本只能靠近似或并行方案了。3. 手写一轮GN代码把每一步摊开看接下来我们直接上一份可以运行的Python实现。我刻意不依赖第三方库只用标准库里的deque和defaultdict方便你边跑边打印中间结果来验证逻辑。3.1 数据结构用什么表示一张图图我用邻接表来表示一个defaultdict键是节点编号值是一个list存所有邻居。对于无向图把每条边在两端各存一次。此外我还需要一个边集合方便判断两条边是否相等以及最后给每条边累计介数。这里有一个设计细节每条无向边我都统一存成 (min(u, v), max(u, v))也就是让小节点编号在前。这样做的目的是避免同一条边在字典里出现两个键比如 (4, 5) 和 (5, 4) 明明是同一条边如果不统一后面统计就会乱套。3.2 核心函数单次边介数计算的完整实现下面这段代码就是Brandes算法的边介数版本。我刻意把变量名写得直接配合注释应该能看明白。from collections import defaultdict, deque def edge_betweenness(n, edge_list): 计算无向图所有边的介数。edge_list 是去重且小端在前的元组列表。 adj defaultdict(list) edge_set set(edge_list) for u, v in edge_list: adj[u].append(v) adj[v].append(u) betweenness {edge: 0.0 for edge in edge_set} for s in range(n): # 阶段一BFS 建树 dist {s: 0} sigma {s: 1} preds defaultdict(list) queue deque([s]) order [] while queue: v queue.popleft() order.append(v) for w in adj[v]: if w not in dist: dist[w] dist[v] 1 queue.append(w) if dist[w] dist[v] 1: sigma[w] sigma[v] preds[w].append(v) # 阶段二反向累积依赖 delta defaultdict(float) for w in reversed(order): for v in preds[w]: contribution (sigma[v] / sigma[w]) * (1.0 delta[w]) edge_key (min(v, w), max(v, w)) betweenness[edge_key] contribution delta[v] contribution # 无向图最短路径会被正反各算一次所以要除以 2 for edge in betweenness: betweenness[edge] / 2.0 return betweenness阶段一里有一个关键细节当 w 已经被访问过时只要它到源点的距离恰好等于 v 的距离加一那么 v 依然要做 w 的前驱。这个条件不能漏否则多条最短路径的计数 sigma 就会算少后面的介数也会跟着错。阶段二中我用 reversed(order) 作为逆序BFS顺序。这里要求 order 必须是BFS的出队顺序而不是按节点编号排序。如果你用递归DFS之类的顺序来做反向遍历依赖累积的传递关系就会坏掉。3.3 删边主循环与分裂记录有了边介数函数GN主循环就简单了。我需要在每次删边后记录当前图的连通分量。def connected_components(n, edge_list): 用并查集返回当前 edge_list 对应的连通分量列表。 parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(a, b): ra, rb find(a), find(b) if ra ! rb: parent[ra] rb for u, v in edge_list: union(u, v) comps defaultdict(list) for i in range(n): comps[find(i)].append(i) return list(comps.values())然后主函数def girvan_newman_trace(n, edges): 执行完整的GN删边过程返回每一步分裂出的连通分量快照。 edge_list list(set((min(u, v), max(u, v)) for u, v in edges)) snapshots [] snapshots.append(connected_components(n, edge_list)) while edge_list: betweenness edge_betweenness(n, edge_list) max_edge max(betweenness, keybetweenness.get) edge_list [e for e in edge_list if e ! max_edge] snapshots.append(connected_components(n, edge_list)) return snapshots这里我采用最严格的GN原版规则每轮只删除介数最大的一条边。如果有多条边介数相同且都最大我取其中一条。这个选择会影响后续分裂轨迹所以如果要复现实验你需要固定一个选择策略不能随机。3.4 小网络运行演示我构造一个完全没有现实背景的小网络0到4号节点构成一个密集社区5到9号节点构成另一个密集社区两个社区之间通过两条桥边相连。这样既方便观察又不需要引入任何外部数据集。edges_demo [ # 左侧社区0、1、2、3、4 (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (0, 3), (0, 4), (3, 4), # 右侧社区5、6、7、8、9 (5, 6), (5, 7), (6, 7), (6, 8), (7, 8), (5, 9), (6, 9), (8, 9), # 两座桥 (4, 5), (2, 8), ] snapshots girvan_newman_trace(10, edges_demo) for idx, comps in enumerate(snapshots): print(fstep {idx}: {comps})运行这个例子你会看到前几步删的都不是桥边因为社区内部替代路径多那些内部边介数反而不高。直到删掉第一条桥边 (4, 5) 后图仍然连通因为还有 (2, 8) 在撑着继续删直到删掉 (2, 8)图才真正分成清清楚楚的两个5节点社区。这个结果能直观验证GN的核心判断介数最高的边通常就是社区之间的桥。4. 常见问题与排查速查写代码分析和跑实验的过程中有几个问题我遇到过不止一次列出来给你当避坑参考。4.1 无向图的边介数要不要除以2这是最容易踩的坑。Brandes算法计算的是“以每个节点为源节点进行累加”对于无向图任何一个无序节点对 {s, t} 的最短路径都会在“以s为源”和“以t为源”这两轮里各被计算一次。也就是说你最终累加出来的每条边的数值是定义里的两倍必须在最后统一除以2。不同教程的处理方式不一样有的在累加时只在对角线一半的邻居上处理有的在最后除以2。我的做法是全程都累加最后统一除以2。这样理解起来最不容易乱。你可以打印一下删边前的最大介数和成熟图算法库的结果对比就知道有没有除2了。4.2 最大介数边有多条时怎么选现实网络里经常出现多条边介数并列最大的情况。严格来说每条候选边删除后分裂出的层次树都可能不同。如果只是为了拿到一个社区划分你可以同时删除所有并列最大的边效率会高很多但如果你想复现论文里的层次结构就必须和原版一样一次删一条并为并列边设定固定的优先规则。还需要注意删掉一条边之后剩余边的介数要全部重算而不是继续沿用上一轮的排序。我自己曾经图省事试图“只重算受影响区域”结果在桥边密集的网络里得到完全错误的社区划分。4.3 怎么确认自己算对了推荐一个很实用的验证方法先用公开的、边数较少的模板网络跑你自己的介数函数打印出每轮介数最高的几条边再找一个成熟的图计算库调用它的边介数函数看看数值是否一致。我通常用两份实现同时跑同一个简单图再逐条边对比一旦发现有边数值对不上就立刻知道是除2的问题、sigma计算问题还是前驱列表的问题。另外一个内部验证技巧是人工挑几条介数应该很高的边用最短路径枚举算一遍理论值。比如由两个全连接子图组成的小网络中间的唯一桥边介数一定接近子图节点数的乘积这是个非常好的手算样例。4.4 图大了跑不动怎么办如果网络边数上万完整GN的 O(m²n) 会非常痛苦。我实际常用的缓解策略有三种。第一用模块度做个终止条件不一定非要删到图里没边只要模块度不再上升就停止这样能省下后面一大半迭代。第二对介数计算做并行Brandes算法的每一轮里不同源节点是完全独立的可以扔进多进程或者用向量化库并行计算每一轮之间虽然不能并行但源节点级别的并行足以把单轮计算压下去不少。第三用GN的近似版本比如只在部分源节点上计算介数或者用抽样的方式估算介数排序这样能换来可接受的结果质量。GN本来就不是为大规模图设计的到了百万级边还是考虑Louvain这类模块度优化算法更现实。5. 用模块度自动选层再加一点个人心得GN删边会生成一整个层次结构但到底哪一层才是最好的社区划分这时候就需要模块度modularity出场。5.1 用模块度挑出最优社区划分模块度Q衡量的是把网络分成若干社区后社区内部的实际连边数比随机连接模型下的期望连边数多多少。Q值越大说明划分结果越能体现“社区内部的边明显比跨社区的边多”这一特征。Q一般在0到1之间0.3以上算是比较明显的社区结构。实现模块度计算时用一个社区归属字典记录每个节点属于哪个社区然后遍历所有节点对累加公式里的值。下面是我常用的简化版本def modularity(n, edge_list, communities): m len(edge_list) if m 0: return 0.0 adj defaultdict(set) for u, v in edge_list: adj[u].add(v) adj[v].add(u) degree {i: len(adj[i]) for i in range(n)} community_of {} for idx, comp in enumerate(communities): for node in comp: community_of[node] idx q 0.0 for u in range(n): for v in range(n): if u v or community_of[u] ! community_of[v]: continue a_uv 1.0 if v in adj[u] else 0.0 q a_uv - (degree[u] * degree[v]) / (2.0 * m) return q / (2.0 * m)在GN主循环的每一步快照上算一次模块度选一个最大的Q对应的快照作为最终社区划分。配合上面手工构造的小网络你会看到模块度在删掉第二座桥、图分裂成两个社区时冲到最高点之后继续删边Q就开始下降说明“过分割”了。5.2 个人实操体会与建议我自己写这个实现踩过最深的坑就是除2问题折腾了一晚上才通过对比查出来。所以建议你哪怕只是练手也一定要找成熟实现做交叉验证不要凭感觉认为自己写对了。另一个体会是GN算法虽然慢但它带给你的“结构解释性”是很多社区发现算法给不了的。每删掉一条边你都知道是为了断开哪个区域之间的连接这对理解网络里的关键通道非常有帮助。如果你当前的需求是快速得到一个社区划分那优先考虑Louvain如果你想理解网络里的“桥梁结构”或者要跑一个教学级演示GN绝对是值得手写一遍的经典。最后分享一个调试技巧别一上来就跑大图先用十几条边的小图跑一遍每轮打印删掉哪条边、当前几个连通分量、每个连通分量长什么样。我看到这些输出之后脑海中才会真正形成“介数高桥社区边界”的直观印象。这也是我建议所有学习者在啃这段代码时一定要亲手打印中间结果的原因。 
长河君 · 2026/10/13 17:44:06 · 阅读 1.2k 社区发现经典算法GN原理与Brandes加速的Python实现
在社交网络分析里社区发现这个话题总结起来就是把一群看起来“抱团”的节点找出来。GN算法Girvan-Newman大概是这类算法里最常被拿来当入门教材的经典它用“边介数edge betweenness”作为标尺一层层剥掉网络里的“桥”让社区自己浮出来。但很多人在代码实现这一步卡住——GN慢慢在反复计算边介数而这背后的加速方案就是常说的fast betweenness算法Brandes算法。这篇文章我会把GN的完整实现思路、fast betweenness的加速原理以及一份可以直接跑起来验证的Python代码一起拆开讲适合正在啃社区发现代码、或者准备自己实现一遍经典图算法的朋友。1. 先搞清楚GN算法到底在求什么社区发现本质上是在回答一个问题一张图里哪些节点天然地聚成一团这个问题不像聚类那样有明确的特征向量图里只有节点和边所以我们只能靠结构信息来判断“抱团”。GN算法给出的答案是社区之间一定有“桥”把桥拆掉社区就出来了。1.1 边介数为什么会成为社区边界的最好裁判你可以把网络想象成一个小镇节点是住户边是道路。社区就是几个联系紧密的居民区。住在同一个居民区里的人来往频繁道路密集不同居民区之间只有少数几条主路相通。如果你想给小镇划分小区最朴素的做法就是找到那些“没有它就不方便串门”的关键道路——这就是边介数的直觉。边介数的正式定义是在一张无向图中对于任意两个节点 s 和 t它们之间有很多条最短路径如果其中某些最短路径经过了边 e那么边 e 就获得一次“贡献”。把所有节点对 s-t 的贡献加起来就得到这条边的介数。直观上介数越高的边越是连接两个区域的咽喉要道去掉它网络就会快速瓦解成两个相对独立的部分。需要注意的是边介数不是“边的度”那种局部指标。一条边的两个端点可能度数都不高但它依然可以是连接两个社区的唯一桥梁反过来社区内部的边即使两端度数很高因为它们的替代路径多介数反而不高。所以边介数天然地能区分“内部边”和“桥梁边”。1.2 从边介数到逐条删边GN的核心操作非常朴素甚至有点暴力计算当前图所有边的介数。找到介数最大的那条边把它删掉。重新计算剩余所有边的介数。重复第2步和第3步直到图里没有边可删。每删一条边这个图可能并不会立即分裂但当删除的边积累到一定程度图会“咔嚓”一声断成两个连通分量。这个“咔嚓”的位置就是一次有意义的社区划分。把所有分裂过程记录下来就形成了一棵层次分裂树也就是dendrogram。这里有个初学者容易误解的地方GN不是“算一次介数然后顺着排序从高到低一口气删完”。每删掉一条边之后剩余边的最短路径关系已经变了之前算出来的介数全部作废。所以主循环里必须每轮重新计算所有边介数。这也是GN复杂度高的重要原因后面我会专门算这笔账。1.3 完整迭代步骤和一个小例子我经常用一张最简单的手工图来理解GN两个五边形通过一条公共边相连。假设左边5个节点内部紧密相连右边5个节点内部也紧密相连中间的桥只有两条边。第一步桥边介数肯定最高先删掉其中一条此时图没断因为还有另一条桥第二步剩下那条桥的介数变成最高再删掉这时图分裂成两个连通分量社区划分完成。从这个例子你也可以看出一次删边未必立刻分裂但每删一条边图的连通性都在发生变化。实际写代码时我们不能只记录“图什么时候断”还应该把“每一步剩余的边集合”保存下来这样才能画出完整的层次结构。2. 关键加速点fast betweenness是如何把你从三层循环里捞出来的很多人误以为GN算法的瓶颈在“删边”本身其实不是。删边是O(1)的操作真正吃时间的是每轮都要重算一遍边介数。而fast betweenness算法也就是Brandes在2001年提出的介数中心性快速算法正是解决这个瓶颈的关键。2.1 朴素办法慢在哪如果按定义去算边介数流程是这样的枚举所有节点对 s-t对每一对节点求一次最短路径再统计哪些最短路径经过了哪些边。最直接的做法甚至可以写成三层循环外层枚举源节点中层枚举目标节点内层做BFS或者Dijkstra。这么做下来单次介数计算就是 O(n³) 的级别非常酸爽。更麻烦的是这种朴素实现里有很多重复劳动。每换一个源节点 s它到所有目标节点的最短路径树都要重新建一次但很多中间结果其实可以在同一棵BFS树里复用。GN算法要反复删边、反复计算介数如果介数计算本身就这么吃力整个算法就只能停留在玩具图上。2.2 Brandes算法的三个关键词BFS树、前驱、累积依赖Brandes算法的聪明之处在于对每一个源节点 s只做一次BFS同时把“从 s 到所有节点的最短路径条数”算出来然后把“所有经过某条边的最短路径贡献”在这一次BFS里累加到对应的边上。具体分两个阶段。第一个阶段还是BFS但是多维护两个东西。一是 sigma[v]表示从源节点 s 到 v 的最短路径条数二是前驱列表 predecessors[v]记录所有可能成为 v 在最短路径上一跳的邻居节点。BFS天然保证非负无权图的层次关系所以当遍历到邻居 w 时如果 dist[w] dist[v] 1说明 v 是 w 的最短路径前驱那么 sigma[w] 就累加上 sigma[v]。第二个阶段是反向累积。从BFS出队的顺序的逆序开始处理每个节点 w对于 w 的每个前驱 v计算一个“依赖值” contribution公式是contribution (sigma[v] / sigma[w]) * (1 delta[w])其中 delta[w] 是之前已经累积到的依赖值。这个值的含义是在所有从源点 s 出发、经过 w 的最短路径里那些通过 w 走向更远节点的路径对边 (v, w) 产生的介数贡献。把 contribution 累加到边 (v, w) 上同时累加到 delta[v] 上以便继续向前传播。这样就做到了一次BFS加上一次反向遍历就能把源节点 s 对所有边的介数贡献全部算完。所有源节点都走一遍边介数就齐了。单次介数计算复杂度从朴素写法的 O(n³) 直接降到 O(mn)在稀疏图上效果尤其明显。2.3 时间与空间复杂度到底怎么算我们来看GN的整体账。设图有 n 个节点、m 条边。Brandes算法计算全部边介数的时间是 O(mn)每次删边后都要重算一遍最多删 m 次所以GN的总复杂度是 O(m²n)。在稀疏图里 m 大约和 n 同阶总复杂度接近 O(n³)在稠密图里 m 接近 n²总复杂度会到 O(n⁵)确实疼。空间方面每一轮介数计算需要存邻接表、sigma、dist、predecessors、delta总空间是 O(mn)。如果网络规模在几千节点、上万边的量级单机Python实现还能撑得住到了百万级边GN就基本只能靠近似或并行方案了。3. 手写一轮GN代码把每一步摊开看接下来我们直接上一份可以运行的Python实现。我刻意不依赖第三方库只用标准库里的deque和defaultdict方便你边跑边打印中间结果来验证逻辑。3.1 数据结构用什么表示一张图图我用邻接表来表示一个defaultdict键是节点编号值是一个list存所有邻居。对于无向图把每条边在两端各存一次。此外我还需要一个边集合方便判断两条边是否相等以及最后给每条边累计介数。这里有一个设计细节每条无向边我都统一存成 (min(u, v), max(u, v))也就是让小节点编号在前。这样做的目的是避免同一条边在字典里出现两个键比如 (4, 5) 和 (5, 4) 明明是同一条边如果不统一后面统计就会乱套。3.2 核心函数单次边介数计算的完整实现下面这段代码就是Brandes算法的边介数版本。我刻意把变量名写得直接配合注释应该能看明白。from collections import defaultdict, deque def edge_betweenness(n, edge_list): 计算无向图所有边的介数。edge_list 是去重且小端在前的元组列表。 adj defaultdict(list) edge_set set(edge_list) for u, v in edge_list: adj[u].append(v) adj[v].append(u) betweenness {edge: 0.0 for edge in edge_set} for s in range(n): # 阶段一BFS 建树 dist {s: 0} sigma {s: 1} preds defaultdict(list) queue deque([s]) order [] while queue: v queue.popleft() order.append(v) for w in adj[v]: if w not in dist: dist[w] dist[v] 1 queue.append(w) if dist[w] dist[v] 1: sigma[w] sigma[v] preds[w].append(v) # 阶段二反向累积依赖 delta defaultdict(float) for w in reversed(order): for v in preds[w]: contribution (sigma[v] / sigma[w]) * (1.0 delta[w]) edge_key (min(v, w), max(v, w)) betweenness[edge_key] contribution delta[v] contribution # 无向图最短路径会被正反各算一次所以要除以 2 for edge in betweenness: betweenness[edge] / 2.0 return betweenness阶段一里有一个关键细节当 w 已经被访问过时只要它到源点的距离恰好等于 v 的距离加一那么 v 依然要做 w 的前驱。这个条件不能漏否则多条最短路径的计数 sigma 就会算少后面的介数也会跟着错。阶段二中我用 reversed(order) 作为逆序BFS顺序。这里要求 order 必须是BFS的出队顺序而不是按节点编号排序。如果你用递归DFS之类的顺序来做反向遍历依赖累积的传递关系就会坏掉。3.3 删边主循环与分裂记录有了边介数函数GN主循环就简单了。我需要在每次删边后记录当前图的连通分量。def connected_components(n, edge_list): 用并查集返回当前 edge_list 对应的连通分量列表。 parent list(range(n)) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] x parent[x] return x def union(a, b): ra, rb find(a), find(b) if ra ! rb: parent[ra] rb for u, v in edge_list: union(u, v) comps defaultdict(list) for i in range(n): comps[find(i)].append(i) return list(comps.values())然后主函数def girvan_newman_trace(n, edges): 执行完整的GN删边过程返回每一步分裂出的连通分量快照。 edge_list list(set((min(u, v), max(u, v)) for u, v in edges)) snapshots [] snapshots.append(connected_components(n, edge_list)) while edge_list: betweenness edge_betweenness(n, edge_list) max_edge max(betweenness, keybetweenness.get) edge_list [e for e in edge_list if e ! max_edge] snapshots.append(connected_components(n, edge_list)) return snapshots这里我采用最严格的GN原版规则每轮只删除介数最大的一条边。如果有多条边介数相同且都最大我取其中一条。这个选择会影响后续分裂轨迹所以如果要复现实验你需要固定一个选择策略不能随机。3.4 小网络运行演示我构造一个完全没有现实背景的小网络0到4号节点构成一个密集社区5到9号节点构成另一个密集社区两个社区之间通过两条桥边相连。这样既方便观察又不需要引入任何外部数据集。edges_demo [ # 左侧社区0、1、2、3、4 (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (0, 3), (0, 4), (3, 4), # 右侧社区5、6、7、8、9 (5, 6), (5, 7), (6, 7), (6, 8), (7, 8), (5, 9), (6, 9), (8, 9), # 两座桥 (4, 5), (2, 8), ] snapshots girvan_newman_trace(10, edges_demo) for idx, comps in enumerate(snapshots): print(fstep {idx}: {comps})运行这个例子你会看到前几步删的都不是桥边因为社区内部替代路径多那些内部边介数反而不高。直到删掉第一条桥边 (4, 5) 后图仍然连通因为还有 (2, 8) 在撑着继续删直到删掉 (2, 8)图才真正分成清清楚楚的两个5节点社区。这个结果能直观验证GN的核心判断介数最高的边通常就是社区之间的桥。4. 常见问题与排查速查写代码分析和跑实验的过程中有几个问题我遇到过不止一次列出来给你当避坑参考。4.1 无向图的边介数要不要除以2这是最容易踩的坑。Brandes算法计算的是“以每个节点为源节点进行累加”对于无向图任何一个无序节点对 {s, t} 的最短路径都会在“以s为源”和“以t为源”这两轮里各被计算一次。也就是说你最终累加出来的每条边的数值是定义里的两倍必须在最后统一除以2。不同教程的处理方式不一样有的在累加时只在对角线一半的邻居上处理有的在最后除以2。我的做法是全程都累加最后统一除以2。这样理解起来最不容易乱。你可以打印一下删边前的最大介数和成熟图算法库的结果对比就知道有没有除2了。4.2 最大介数边有多条时怎么选现实网络里经常出现多条边介数并列最大的情况。严格来说每条候选边删除后分裂出的层次树都可能不同。如果只是为了拿到一个社区划分你可以同时删除所有并列最大的边效率会高很多但如果你想复现论文里的层次结构就必须和原版一样一次删一条并为并列边设定固定的优先规则。还需要注意删掉一条边之后剩余边的介数要全部重算而不是继续沿用上一轮的排序。我自己曾经图省事试图“只重算受影响区域”结果在桥边密集的网络里得到完全错误的社区划分。4.3 怎么确认自己算对了推荐一个很实用的验证方法先用公开的、边数较少的模板网络跑你自己的介数函数打印出每轮介数最高的几条边再找一个成熟的图计算库调用它的边介数函数看看数值是否一致。我通常用两份实现同时跑同一个简单图再逐条边对比一旦发现有边数值对不上就立刻知道是除2的问题、sigma计算问题还是前驱列表的问题。另外一个内部验证技巧是人工挑几条介数应该很高的边用最短路径枚举算一遍理论值。比如由两个全连接子图组成的小网络中间的唯一桥边介数一定接近子图节点数的乘积这是个非常好的手算样例。4.4 图大了跑不动怎么办如果网络边数上万完整GN的 O(m²n) 会非常痛苦。我实际常用的缓解策略有三种。第一用模块度做个终止条件不一定非要删到图里没边只要模块度不再上升就停止这样能省下后面一大半迭代。第二对介数计算做并行Brandes算法的每一轮里不同源节点是完全独立的可以扔进多进程或者用向量化库并行计算每一轮之间虽然不能并行但源节点级别的并行足以把单轮计算压下去不少。第三用GN的近似版本比如只在部分源节点上计算介数或者用抽样的方式估算介数排序这样能换来可接受的结果质量。GN本来就不是为大规模图设计的到了百万级边还是考虑Louvain这类模块度优化算法更现实。5. 用模块度自动选层再加一点个人心得GN删边会生成一整个层次结构但到底哪一层才是最好的社区划分这时候就需要模块度modularity出场。5.1 用模块度挑出最优社区划分模块度Q衡量的是把网络分成若干社区后社区内部的实际连边数比随机连接模型下的期望连边数多多少。Q值越大说明划分结果越能体现“社区内部的边明显比跨社区的边多”这一特征。Q一般在0到1之间0.3以上算是比较明显的社区结构。实现模块度计算时用一个社区归属字典记录每个节点属于哪个社区然后遍历所有节点对累加公式里的值。下面是我常用的简化版本def modularity(n, edge_list, communities): m len(edge_list) if m 0: return 0.0 adj defaultdict(set) for u, v in edge_list: adj[u].add(v) adj[v].add(u) degree {i: len(adj[i]) for i in range(n)} community_of {} for idx, comp in enumerate(communities): for node in comp: community_of[node] idx q 0.0 for u in range(n): for v in range(n): if u v or community_of[u] ! community_of[v]: continue a_uv 1.0 if v in adj[u] else 0.0 q a_uv - (degree[u] * degree[v]) / (2.0 * m) return q / (2.0 * m)在GN主循环的每一步快照上算一次模块度选一个最大的Q对应的快照作为最终社区划分。配合上面手工构造的小网络你会看到模块度在删掉第二座桥、图分裂成两个社区时冲到最高点之后继续删边Q就开始下降说明“过分割”了。5.2 个人实操体会与建议我自己写这个实现踩过最深的坑就是除2问题折腾了一晚上才通过对比查出来。所以建议你哪怕只是练手也一定要找成熟实现做交叉验证不要凭感觉认为自己写对了。另一个体会是GN算法虽然慢但它带给你的“结构解释性”是很多社区发现算法给不了的。每删掉一条边你都知道是为了断开哪个区域之间的连接这对理解网络里的关键通道非常有帮助。如果你当前的需求是快速得到一个社区划分那优先考虑Louvain如果你想理解网络里的“桥梁结构”或者要跑一个教学级演示GN绝对是值得手写一遍的经典。最后分享一个调试技巧别一上来就跑大图先用十几条边的小图跑一遍每轮打印删掉哪条边、当前几个连通分量、每个连通分量长什么样。我看到这些输出之后脑海中才会真正形成“介数高桥社区边界”的直观印象。这也是我建议所有学习者在啃这段代码时一定要亲手打印中间结果的原因。