COMP5313 Tutorial 04 — Graphs 详细题解

图结构勘误：Tutorial PDF 的图 3 文字描述与 Exercise 3 NetworkX 代码片段的边集不一致。以 NetworkX 代码为准，图 3 共有 10 条边，而非 9 条。具体边集见下方。

---

图 1 回顾

边集（无向图）：A-B, A-C, A-F, B-C, B-G, C-F, D-E, F-G, F-E（共 9 条）

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

---

Exercise 1：BFS

a) 网络有多少条边？

答案：9 条边

edges = ['A-B','A-C','A-F','B-C','B-G','C-F','D-E','F-G','F-E']
print(len(edges))  # 9

b) 有向还是无向？

答案：无向图。题目没有箭头，表示边无方向。

c) 网络是否连通？

答案：是连通的。任意两个节点都可以通过某条路径到达。

验证（Python 自检）：

# 验证连通性：BFS 从任意节点出发能到达所有节点
from collections import deque

edges = [('A','B'),('A','C'),('A','F'),('B','C'),('B','G'),('C','F'),('D','E'),('F','G'),('F','E')]
G = {u:set() for u in 'ABCDEFG'}
for u,v in edges:
    G[u].add(v); G[v].add(u)

def bfs_component(start):
    visited = set()
    q = deque([start])
    while q:
        u = q.popleft()
        if u in visited: continue
        visited.add(u)
        for v in G[u]:
            if v not in visited: q.append(v)
    return visited

comp = bfs_component('B')
print(sorted(comp))  # ['A','B','C','D','E','F','G'] → 7个节点全部连通

d) 从 B 出发 BFS 的访问顺序？

答案：B, A, C, G, F, D, E（同一层节点顺序任意）

BFS 分层过程： | 层 | 节点 | |---|------| | 0 | B | | 1 | A, C, G（A、C 与 B 相邻；G 通过 B-C 路径也可到达，但先被访问） | | 2 | F（A 的邻居；也通过 C 到达） | | 3 | D, E（F 的邻居） |

---

Exercise 2：Triadic Closure 与 STC

强三元闭包（Strong Triadic Closure，STC）

STC 定义：若节点 \(v\) 与两个邻居 \(x\)、\(y\) 有强关系，则 \(x\) 与 \(y\) 之间必须至少是弱关系。

触发条件：当一个节点有两个强邻居，且这两个强邻居之间无边（无任何关系）时，违反 STC。

图 2 分析

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

边集：A-B(strong), B-C(weak), A-C(weak), C-D(weak), D-E(strong), E-F(weak), B-E(strong)

逐节点检查：

节点	强邻居对	两强邻居之间是否有边？	违反 STC？
A	—	—	否
B	E, C	无边（B 的强邻居 E 和 C 之间无边）	是 → B 违反 STC
C	—	—	否
D	E	只有一个强邻居	否
E	B, D	无边（E 的强邻居 B 和 D 之间无边）	是 → E 违反 STC
F	—	—	否

答案：违反 STC 的节点是 E 和 B。

---

Exercise 3：Embeddedness 与 Betweenness

图 3 边集（以 NetworkX 代码为准）

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

边集（共 10 条）： A-B, A-G, B-C, G-E, E-C, G-F, D-C, F-E, E-D, F-D

⚠️ 勘误：Tutorial PDF 中图 3 的文字描述可能与 NetworkX 代码片段的边集不一致（PDF 文字描述缺少 G-F 等边）。以 Exercise 3(b) 答案中出现的边和 NetworkX 代码为准。

a) Embeddedness（嵌入度）

\[\text{embeddedness}(u,v) = |N(u) \setminus \{v\} \cap N(v) \setminus \{u\}|\]

即两个端点的共同邻居数量（排除彼此）。

边	端点邻居	共同邻居	Embeddedness
(A,B)	\(N(A)=\{B,G\},\; N(B)=\{A,C\}\)	\(\emptyset\)	0
(D,F)	\(N(D)=\{C,E,F\},\; N(F)=\{G,E,D\}\)	\(\{E\}\)	1

答案： - Embeddedness of (A,B) = 0（A 和 B 无共同邻居） - Embeddedness of (D,F) = 1（D 和 F 的共同邻居只有 E）

a) Betweenness（介数中心性）

Tutorial 给出的非标准化 betweenness（以"flow"计量，路径对之间均分）：

边	Betweenness
(A,B)	3.667
(D,F)	2.667

计算过程（以 (A,B) 为例）：

\(A \to B\)：直接路径 → 贡献 1
\(A \to C\)：两条最短路径 \(A\)-\(B\)-\(C\)、\(A\)-\(G\)-\(E\)-\(C\)；只有 \(A\)-\(B\)-\(C\) 通过 (A,B) → 贡献 \(\frac{1}{2}\)
\(B \to G\)：两条最短路径 \(B\)-\(A\)-\(G\)、\(B\)-\(C\)-\(E\)-\(G\)；只有 \(B\)-\(A\)-\(G\) 通过 (A,B) → 贡献 \(\frac{1}{2}\)
\(B \to F\)：三条最短路径；只有 \(B\)-\(A\)-\(G\)-\(F\) 通过 (A,B) → 贡献 \(\frac{1}{3}\)
\(D \to A\)：三条最短路径；只有 \(D\)-\(E\)-\(G\)-\(A\) 通过 (A,B) → 贡献 \(\frac{1}{3}\)

\[\text{Betweenness}(A,B) = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \frac{1}{3} = 3.667\]

b) Bridge vs. Local Bridge

Definitions：

• Local bridge：两端点没有共同邻居（即 embeddedness = 0）的边
• Bridge：删除后图不再连通的边
• Span：删除一条边后，两端点之间新距离（最短路径长度）

分析边 (A,B)：

• Embeddedness(A,B) = 0 → (A,B) 是 Local bridge（是局部桥）
• 删除 (A,B) 后，A 与 B 仍然连通（路径：A-G-E-C-B），但距离从 1 跳变为 4 跳（A-G-E-C-B）
• 因此 span = 4
• A 与 B 在移除后仍连通 → 不是 Bridge（因为不是全桥）

答案：(A,B) 是 Local bridge，span = 4，不是 Bridge。

---

Exercise 4：Girvan-Newman 与 Betweenness

完整图所有边的 Betweenness

边	Betweenness
(A,G)	5.000
(B,C)	5.000
(G,E)	3.833
(E,C)	3.833
(A,B)	3.667
(G,F)	3.167
(D,C)	3.167
(F,D)	2.667
(F,E)	1.833
(E,D)	1.833

Girvan-Newman 迭代过程

Iteration 1：移除 (A,G) 和 (B,C)（betweenness 最高 = 5）

• Region 1: {A, B}
• Region 2: {C, D, E, F, G}

Iteration 2：移除 (E,C) 和 (E,G)（betweenness = 3.833）

• Region 1: {A, B}（不变）
• Region 2: {C, D, E, F, G}（不变）

Iteration 3：移除 (G,F)、(F,D)、(D,C)

最终 Level 2 regions：

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

NetworkX 验证代码

import networkx as nx

g = nx.Graph()
g.add_edges_from([
    ('A','B'),('A','G'),('B','C'),
    ('G','E'),('E','C'),('G','F'),
    ('D','C'),('F','E'),('E','D'),('F','D')
])

eb = nx.edge_betweenness_centrality(g, normalized=False)
for e, v in sorted(eb.items(), key=lambda x: -x[1]):
    print(f'{e}: {v:.3f}')

# Iteration 1: 最高 betweenness 边 (A,G) 和 (B,C)
g.remove_edge('A','G')
g.remove_edge('B','C')
print('After iter 1 regions:', nx.number_connected_components(g))

# Iteration 2: 最高 betweenness 边 (E,C) 和 (E,G)
g.remove_edge('E','C')
g.remove_edge('E','G')
print('After iter 2 regions:', nx.number_connected_components(g))

# Iteration 3: 移除 (G,F), (F,D), (D,C)
g.remove_edge('G','F')
g.remove_edge('F','D')
g.remove_edge('D','C')
print('After iter 3 components:')
for comp in nx.connected_components(g):
    print(sorted(comp))

---

参考信息

• Tutorial PDF：/Users/joey/.openclaw/workspace-comp5313/files/tutorials/04_lab_Graphs_with_answers.pdf
• SID: 550378747 | Author: Yi Qiao