COMP5313 Assignment 1 题解（五）

Posted on Edited on In Word count in article: 1.2k Reading time ≈ 4 mins.
对 Figure 5 使用 Girvan-Newman partitioning method，写出

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 的图结构

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

  • \(A\)--\(C\)
  • \(A\)--\(D\)
  • \(B\)--\(C\)
  • \(B\)--\(D\)
  • \(C\)--\(E\)
  • \(D\)--\(F\)
  • \(E\)--\(F\)
  • \(E\)--\(G\)
  • \(F\)--\(G\)

所以图可以写成：

\[ E = \{AC, AD, BC, BD, CE, DF, EF, EG, FG\}. \]

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

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

  • 左边：\(\{A,B,C,D\}\)
  • 右边：\(\{E,F,G\}\)
  • 中间连接边：\(CE\) 和 \(DF\)

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

3. Girvan-Newman 方法回顾

Girvan-Newman 的规则是：

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

4. Level 0

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

\[ \boxed{\{A,B,C,D,E,F,G\}} \]

5. 第一轮删除

5.1 为什么 \(CE\) 和 \(DF\) 的 betweenness 最高

边 \(CE\) 和 \(DF\) 连接了左边子图与右边子图。

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

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

\[ CE,\ DF \]

所以第一轮删除：

\[ CE,\ DF \]

5.2 删除后的连通分量

删掉 \(CE\) 和 \(DF\) 后，图被分成两块：

  • 左边：\(\{A,B,C,D\}\)
  • 右边：\(\{E,F,G\}\)

所以 Level 1 的 nested regions 是：

\[ \boxed{\{A,B,C,D\},\ \{E,F,G\}} \]

6. 第二轮删除

现在对两个子图分别看：

左边子图 \(\{A,B,C,D\}\)

它的边是：

  • \(AC\)
  • \(AD\)
  • \(BC\)
  • \(BD\)

这实际上是一个 4-cycle：

\[ A - C - B - D - A \]

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

右边子图 \(\{E,F,G\}\)

它是一个三角形：

  • \(EF\)
  • \(EG\)
  • \(FG\)

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

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

\[ AC,\ AD,\ BC,\ BD \]

因此第二轮删除：

\[ AC,\ AD,\ BC,\ BD \]

6.1 删除后的连通分量

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

\[ \{A\},\ \{B\},\ \{C\},\ \{D\} \]

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

\[ \{E,F,G\} \]

所以 Level 2 的 nested regions 是：

\[ \boxed{\{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E,F,G\}} \]

7. 第三轮删除

此时只剩右边三角形：

  • \(EF\)
  • \(EG\)
  • \(FG\)

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

删除后得到：

\[ \{E\},\ \{F\},\ \{G\} \]

所以 Level 3 的 nested regions 是：

\[ \boxed{\{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E\},\ \{F\},\ \{G\}} \]

8. 最终 nested regions

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

Level 0

\[ \boxed{\{A,B,C,D,E,F,G\}} \]

Level 1

\[ \boxed{\{A,B,C,D\},\ \{E,F,G\}} \]

Level 2

\[ \boxed{\{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E,F,G\}} \]

Level 3

\[ \boxed{\{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E\},\ \{F\},\ \{G\}} \]

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

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

\[ \{A,B,C,D,E,F,G\} \]

\[ \{A,B,C,D\},\ \{E,F,G\} \]

\[ \{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E,F,G\} \]

\[ \{A\},\ \{B\},\ \{C\},\ \{D\},\ \{E\},\ \{F\},\ \{G\} \]

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))

COMP5313