COMP5313 Assignment 1 题解 05 - Girvan-Newman

Posted on 2026-03-26 Edited on 2026-03-30 In Course , COMP5313 Word count in article: 1.2k Reading time ≈ 4 mins.

COMP5313 Assignment 1 题解（五）

Task 5 — Girvan-Newman

题目

对 Figure 5 使用 Girvan-Newman partitioning method，写出这个图在每一层分割过程中得到的 nested regions，也就是每一层的 connected components / regions。

这一题要求用 Girvan-Newman partitioning method 给出图的 nested regions，也就是：

第 0 层，整个图是一个 region；
然后不断删除 edge betweenness 最高的边；
每删完一轮后，记录当前图被分成了哪些 connected components；
这些 connected components 就是该层的 regions。

1. Figure 5 的图结构

根据题图，可以把边读成：

所以图可以写成：

2. Mermaid 重构图

graph LR
    A((A))
    B((B))
    C((C))
    D((D))
    E((E))
    F((F))
    G((G))

    A --- C
    A --- D
    B --- C
    B --- D
    C --- E
    D --- F
    E --- F
    E --- G
    F --- G

从结构上看，这个图其实像是两块通过两条“桥”连在一起：

左边：
右边：
中间连接边：和

所以按直觉，第一轮被删掉的应该就是这两条跨社区的边。

3. Girvan-Newman 方法回顾

Girvan-Newman 的规则是：

计算所有边的 edge betweenness；
删除 betweenness 最高的边；
重新计算剩余图中的 edge betweenness；
重复，直到图被不断拆分；
记录每一层的 connected components，也就是 nested regions。

4. Level 0

初始时整张图是连通的，所以只有一个 region：

5. 第一轮删除

5.1 为什么和的 betweenness 最高

边和连接了左边子图与右边子图。

很多从左边到右边的最短路径都必须经过这两条边之一，因此它们的 edge betweenness 最大。

计算后可得，这一轮最高的是：

所以第一轮删除：

5.2 删除后的连通分量

删掉和后，图被分成两块：

左边：
右边：

所以 Level 1 的 nested regions 是：

6. 第二轮删除

现在对两个子图分别看：

左边子图

它的边是：

这实际上是一个 4-cycle：

在这个结构里，四条边对称，因此 betweenness 相同。

右边子图

它是一个三角形：

三角形中三条边也完全对称。

重新计算后，这一轮最高的是左边四条边：

因此第二轮删除：

6.1 删除后的连通分量

左边四个点会彻底分裂成单点：

右边三角形仍然保持连通：

所以 Level 2 的 nested regions 是：

7. 第三轮删除

此时只剩右边三角形：

三条边对称，betweenness 相同，因此一起删掉后，右边三角形也被拆成三个单点。

删除后得到：

所以 Level 3 的 nested regions 是：

8. 最终 nested regions

因此，这个图的 nested regions 按层写为：

Level 0

Level 1

Level 2

Level 3

9. 最后可直接写成答案的形式

The nested regions obtained by the Girvan-Newman method are:

10. Python 验证代码

from collections import defaultdict, deque

nodes = list('ABCDEFG')
edges = [
    ('A', 'C'), ('A', 'D'),
    ('B', 'C'), ('B', 'D'),
    ('C', 'E'), ('D', 'F'),
    ('E', 'F'), ('E', 'G'), ('F', 'G')
]


def components(nodes, edges):
    G = {u: set() for u in nodes}
    for u, v in edges:
        G[u].add(v)
        G[v].add(u)

    seen = set()
    comps = []
    for u in nodes:
        if u in seen:
            continue
        q = [u]
        seen.add(u)
        comp = []
        while q:
            x = q.pop()
            comp.append(x)
            for y in G[x]:
                if y not in seen:
                    seen.add(y)
                    q.append(y)
        comps.append(tuple(sorted(comp)))
    return tuple(sorted(comps))


def edge_betweenness(nodes, edges):
    G = {u: set() for u in nodes}
    for u, v in edges:
        G[u].add(v)
        G[v].add(u)

    def all_shortest_paths(s, t):
        q = deque([s])
        dist = {s: 0}
        parents = defaultdict(list)
        while q:
            u = q.popleft()
            for v in G[u]:
                if v not in dist:
                    dist[v] = dist[u] + 1
                    parents[v].append(u)
                    q.append(v)
                elif dist[v] == dist[u] + 1:
                    parents[v].append(u)

        paths = []
        def backtrack(x, path):
            if x == s:
                paths.append(list(reversed(path + [x])))
                return
            for p in parents[x]:
                backtrack(p, path + [x])
        backtrack(t, [])
        return paths

    score = defaultdict(float)
    for i, s in enumerate(nodes):
        for t in nodes[i + 1:]:
            paths = all_shortest_paths(s, t)
            for path in paths:
                for j in range(len(path) - 1):
                    e = tuple(sorted((path[j], path[j + 1])))
                    score[e] += 1 / len(paths)
    return score

cur_edges = edges[:]
print('Level 0:', components(nodes, cur_edges))

for level in range(1, 4):
    bet = edge_betweenness(nodes, cur_edges)
    mx = max(bet.values())
    remove_edges = [e for e, v in bet.items() if v == mx]
    cur_edges = [e for e in cur_edges if tuple(sorted(e)) not in remove_edges]
    print(f'Level {level}:', components(nodes, cur_edges))