COMP5313 Assignment 1 题解

Posted on Edited on In Word count in article: 7.9k Reading time ≈ 29 mins.
COMP5313 Assignment 1 全部 5 个 task 的题解合集 —— Strong/Weak Ties、Link Formation、Structural Balance、Network Bottlenecks、Girvan-Newman。

COMP5313 Assignment 1 题解

本文合并 Assignment 1 的全部 5 个 task 题解，依次为：Strong and Weak Ties、Link Formation、Structural Balance、Network Bottlenecks、Girvan-Newman。

Task 1 — Strong and Weak Ties

题目

给定 Figure 1 中的社交网络，其中每条边都标记为 strong tie 或 weak tie。题目要求判断：是否所有节点都满足 Strong Triadic Closure Property (STC)；如果不是，需要列出所有违反该性质的节点。

这一题考的是 Strong Triadic Closure Property, 简称 STC。

它本质上是在问：

如果一个人和两个人都是“强关系”，那么这两个人之间是否至少也认识？

如果答案是否定的，那么这个节点就违反了 STC。

1. 题目目标

题目要求：

  1. 判断图中是否 所有节点 都满足 Strong Triadic Closure Property；
  2. 如果不是，列出所有违反该性质的节点。

2. STC 的直观理解

设某个节点是 \(u\)，它和两个邻居 \(v,w\) 都是 strong ties。

那么 STC 要求：

\[ (u,v) \text{ is strong and } (u,w) \text{ is strong} \implies (v,w) \in E. \]

这里 \((v,w) \in E\) 的意思是：

  • \(v\) 和 \(w\) 之间至少要有一条边；
  • 这条边可以是 strong，也可以是 weak。

所以 STC 检查的是：

  • 不是要求形成一个全是 strong 的三角形；
  • 只要求这两个 strong neighbors 之间 不要断开。

3. Figure 1 的图结构整理

根据题图，可以把节点和边整理出来。

节点集合为：

\[ V = \{A,B,C,D,E\}. \]

边集合为：

  • \(A\)--\(B\): strong
  • \(A\)--\(C\): strong
  • \(A\)--\(E\): weak
  • \(B\)--\(D\): weak
  • \(B\)--\(E\): strong
  • \(C\)--\(D\): weak
  • \(C\)--\(E\): strong
  • \(D\)--\(E\): weak

因此：

\[ E = \{AB, AC, AE, BD, BE, CD, CE, DE\}. \]

其中 strong edges 为：

\[ E_s = \{AB, AC, BE, CE\}. \]

weak edges 为：

\[ E_w = \{AE, BD, CD, DE\}. \]

4. 用 Mermaid 画出结构示意

下面这个图不是原题扫描图，而是我根据题目重构的结构图，便于看题解逻辑。

graph TD
    A((A))
    B((B))
    C((C))
    D((D))
    E((E))

    A ---|s| B
    A ---|s| C
    A ---|w| E
    B ---|w| D
    B ---|s| E
    C ---|w| D
    C ---|s| E
    D ---|w| E

从这个结构里最关键的观察是：

  • \(B\) 和 \(C\) 没有直接边；
  • 但 \(A\) 同时和 \(B,C\) 是 strong；
  • \(E\) 也同时和 \(B,C\) 是 strong。

所以这两个点很可能违反 STC。

5. 解题策略

这一题最稳妥的方法是：逐个节点检查 strong neighbors。

通用步骤

对于每个节点 \(u\)：

  1. 找出所有与 \(u\) 通过 strong edge 相连的邻居；
  2. 如果 strong neighbors 少于 2 个，那么 \(u\) 自动满足 STC；
  3. 如果 strong neighbors 至少有 2 个，就检查这些 strong neighbors 两两之间是否有边；
  4. 只要存在一对 strong neighbors 之间没有边，那么 \(u\) 就违反 STC。

6. 逐点详细检查

6.1 Node \(A\)

与 \(A\) 相连的边有：

  • \(AB\)：strong
  • \(AC\)：strong
  • \(AE\)：weak

所以 \(A\) 的 strong neighbors 是：

\[ N_s(A) = \{B,C\}. \]

现在检查 \(B\) 和 \(C\) 之间是否有边。

观察图可知：

\[ BC \notin E. \]

也就是说，\(A\) 有两个 strong neighbors，但这两个节点彼此之间不相连。

因此：

\[ A \text{ violates STC.} \]

6.2 Node \(B\)

与 \(B\) 相连的边有：

  • \(AB\)：strong
  • \(BE\)：strong
  • \(BD\)：weak

所以 \(B\) 的 strong neighbors 是：

\[ N_s(B) = \{A,E\}. \]

检查 \(A\) 和 \(E\) 之间是否有边。

图中有：

\[ AE \in E, \]

并且它是 weak edge。

注意，这里 weak edge 也够了，因为 STC 只要求 “存在边”，不要求这条边也是 strong。

因此：

\[ B \text{ satisfies STC.} \]

6.3 Node \(C\)

与 \(C\) 相连的边有：

  • \(AC\)：strong
  • \(CE\)：strong
  • \(CD\)：weak

所以 \(C\) 的 strong neighbors 是：

\[ N_s(C) = \{A,E\}. \]

检查 \(A\) 和 \(E\) 是否相连。

由于图中有 weak edge \(AE\)，因此：

\[ AE \in E. \]

所以：

\[ C \text{ satisfies STC.} \]

6.4 Node \(D\)

与 \(D\) 相连的边有：

  • \(BD\)：weak
  • \(CD\)：weak
  • \(DE\)：weak

所以 \(D\) 没有 strong tie。

也就是说：

\[ N_s(D) = \varnothing. \]

因为 strong neighbors 少于 2 个，\(D\) 不可能构成违反 STC 的情形，因此自动满足。

所以：

\[ D \text{ satisfies STC.} \]

6.5 Node \(E\)

与 \(E\) 相连的边有：

  • \(BE\)：strong
  • \(CE\)：strong
  • \(AE\)：weak
  • \(DE\)：weak

所以 \(E\) 的 strong neighbors 是：

\[ N_s(E) = \{B,C\}. \]

现在检查 \(B\) 和 \(C\) 之间是否有边。

图中没有 \(BC\) 这条边，因此：

\[ BC \notin E. \]

于是 \(E\) 也有两个 strong neighbors，但这两个 neighbors 彼此不相连。

所以：

\[ E \text{ violates STC.} \]

7. 总结表格

Node Strong neighbors 这些 strong neighbors 之间是否有边 是否满足 STC
\(A\) \(\{B,C\}\) 否 否
\(B\) \(\{A,E\}\) 是，\(AE\) 存在 是
\(C\) \(\{A,E\}\) 是，\(AE\) 存在 是
\(D\) \(\varnothing\) 不需要检查 是
\(E\) \(\{B,C\}\) 否 否

8. 最终答案

并不是所有节点都满足 Strong Triadic Closure Property。

违反该性质的节点是：

\[ \boxed{A \text{ and } E}. \]

10. 用 Python / NetworkX 验证

虽然这题完全可以手算，但也可以用代码验证你的结论。

下面是一个简单的 Python 思路。

import networkx as nx
from itertools import combinations

G = nx.Graph()

# add edges with tie labels
edges = [
    ('A', 'B', 's'),
    ('A', 'C', 's'),
    ('A', 'E', 'w'),
    ('B', 'D', 'w'),
    ('B', 'E', 's'),
    ('C', 'D', 'w'),
    ('C', 'E', 's'),
    ('D', 'E', 'w'),
]

for u, v, tie in edges:
    G.add_edge(u, v, tie=tie)

violations = []

for u in G.nodes():
    strong_neighbors = [
        v for v in G.neighbors(u)
        if G[u][v]['tie'] == 's'
    ]

    ok = True
    for v, w in combinations(strong_neighbors, 2):
        if not G.has_edge(v, w):
            ok = False
            break

    if not ok:
        violations.append(u)

print('Violating nodes:', violations)

运行结果应为：

Violating nodes: ['A', 'E']

11. 这题最容易错的地方

错误 1：把 weak edge 当成“不算边”

这是最常见错误。

STC 要求的是 strong neighbors 之间 有边即可，不管这条边是 strong 还是 weak。

所以像 \(AE\) 虽然是 weak，但它依然足以让：

  • \(B\) 满足 STC；
  • \(C\) 满足 STC。

错误 2：检查了所有邻居，而不是只检查 strong neighbors

STC 只关心某个节点的 strong ties。

weak ties 不会触发 STC 检查。

错误 3：觉得没有 strong ties 的点“不知道算不算满足”

像 \(D\) 这种点没有两个 strong neighbors，自然不可能违反定义，因此默认满足。

12. 一句话记忆

这题可以记成一句话：

谁同时通过 strong tie 连到 \(B\) 和 \(C\)，而 \(B,C\) 又没边，谁就违反 STC。

在这张图里，正好就是：

\[ \boxed{A, E}. \]

COMP5313

题目

根据 Figure 2 的社交网络，回答四个问题：

  1. 边 \((A,B)\) 的 neighborhood overlap 是多少；
  2. 节点 \(D\) 和 \(E\) 中，谁的 clustering coefficient 更高；
  3. 如果将来网络继续演化，根据 triadic closure，哪一条新边最可能出现；
  4. 边 \((B,D)\) 的 betweenness 是多少。

其中第 (iv) 问要求手算，不应只用程序代替过程。

这一题把几个 lecture 里的核心概念放在了一起：

  1. Neighborhood overlap
  2. Clustering coefficient
  3. Triadic closure / link formation
  4. Edge betweenness

如果这些词看着很抽象，可以先把它们理解成：

  • Neighborhood overlap：两个人的共同朋友比例高不高；
  • Clustering coefficient：一个人的朋友之间彼此熟不熟；
  • Triadic closure：两个人共同朋友越多，越容易在未来连边；
  • Edge betweenness：一条边是不是很多最短路径都会经过的“关键通道”。

所以这题其实就是从两个角度看这个图：

  • 看局部：一个点周围是不是很紧密；
  • 看整体：哪条边在整张图里更关键。

1. Figure 2 的图结构

根据题图，节点为：

\[ V = \{A,B,C,D,E,F\}. \]

边为：

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

因此：

\[ E = \{AB, AC, AE, AF, BC, BD, DE, DF, EF\}. \]

2. Mermaid 重构图

为了后面分析方便，可以把 Figure 2 重构成下面这个图：

graph TD
    A((A))
    B((B))
    C((C))
    D((D))
    E((E))
    F((F))

    A --- B
    A --- C
    B --- C

    A --- E
    A --- F
    E --- F

    B --- D
    D --- E
    D --- F

从这个图里可以先看出两个局部结构：

  • 左上角有三角形 \(A\)-\(B\)-\(C\)
  • 左侧还有三角形 \(A\)-\(E\)-\(F\)
  • 节点 \(D\) 连向 \(B,E,F\)

这对后面算 clustering coefficient 和 edge betweenness 很重要。

3. 各节点邻居集合

先把每个节点的邻居列出来，后面所有小问都会用到。

\[ N(A) = \{B,C,E,F\} \]

\[ N(B) = \{A,C,D\} \]

\[ N(C) = \{A,B\} \]

\[ N(D) = \{B,E,F\} \]

\[ N(E) = \{A,D,F\} \]

\[ N(F) = \{A,D,E\} \]

4. Question (i)

What is the neighborhood overlap of edge \((A,B)\)?

4.1 定义

这一问其实就是在算：

对于已经相连的两个人 \(u\) 和 \(v\)，他们的朋友圈有多像？

Neighborhood overlap 可以写成：

\[ O(u,v)=\frac{\text{共同邻居数}}{\text{合并后的邻居总数}} \]

如果严格写成集合形式，就是：

\[ O(u,v)=\frac{|(N(u)\setminus\{v\})\cap(N(v)\setminus\{u\})|}{|(N(u)\setminus\{v\})\cup(N(v)\setminus\{u\})|} \]

这里：

  • \(N(u)\) 表示节点 \(u\) 的邻居集合；
  • \(N(u)\setminus\{v\}\) 表示把对方节点先去掉；
  • 分子是共同邻居；
  • 分母是两边邻居合起来以后去重的总数。

所以你可以把它直接记成：

\[ \text{overlap} = \frac{\text{共同朋友}}{\text{总朋友（去重后）}} \]

4.2 先求去掉彼此后的邻居集合

对于边 \((A,B)\)：

\[ N(A) \setminus \{B\} = \{C,E,F\} \]

\[ N(B) \setminus \{A\} = \{C,D\} \]

共同邻居是：

\[ \{C,E,F\} \cap \{C,D\} = \{C\} \]

所以分子为：

\[ 1 \]

并集是：

\[ \{C,E,F\} \cup \{C,D\} = \{C,D,E,F\} \]

所以分母为：

\[ 4 \]

4.3 得到 overlap

因此：

\[ O(A,B)=\frac{1}{4}. \]

4.4 答案

\[ \boxed{\text{Neighborhood overlap of }(A,B)=\frac{1}{4}} \]

5. Question (ii)

Between nodes \(D\) and \(E\), which one has a higher clustering coefficient?

5.1 定义

Clustering coefficient 看的是：

一个节点的朋友之间，彼此连接得有多紧。

如果节点 \(u\) 有很多邻居，但这些邻居彼此几乎不认识，那么它的 clustering coefficient 就低； 如果这些邻居彼此之间连得很密，那么这个值就高。

公式写成：

\[ C(u)=\frac{\text{邻居之间实际存在的边数}}{\text{邻居之间最多可能存在的边数}} \]

如果节点 \(u\) 的度数是 \(k_u\)，那么它的邻居之间最多可能有：

\[ \binom{k_u}{2} = \frac{k_u(k_u-1)}{2} \]

条边。

所以也可以写成：

\[ C(u)=\frac{\#\text{ of edges among neighbors of }u}{\binom{k_u}{2}} \]

你可以把它理解成：

\[ \text{clustering coefficient} = \frac{\text{实际形成了多少个“朋友之间的连接”}}{\text{理论上最多能有多少个}} \]

5.2 计算 \(D\) 的 clustering coefficient

\(D\) 的邻居是：

\[ N(D)=\{B,E,F\} \]

所以 \(k_D=3\)，最大可能边数为：

\[ \binom{3}{2}=3. \]

现在检查 \(B,E,F\) 之间有哪些边：

  • \(B\)--\(E\)：不存在
  • \(B\)--\(F\)：不存在
  • \(E\)--\(F\)：存在

所以实际存在的边数是：

\[ 1 \]

因此：

\[ C(D)=\frac{1}{3}. \]

5.3 计算 \(E\) 的 clustering coefficient

\(E\) 的邻居是：

\[ N(E)=\{A,D,F\} \]

所以 \(k_E=3\)，最大可能边数也是：

\[ \binom{3}{2}=3. \]

检查 \(A,D,F\) 之间有哪些边：

  • \(A\)--\(D\)：不存在
  • \(A\)--\(F\)：存在
  • \(D\)--\(F\)：存在

所以实际存在的边数是：

\[ 2 \]

因此：

\[ C(E)=\frac{2}{3}. \]

5.4 比较

因为：

\[ \frac{2}{3} > \frac{1}{3} \]

所以：

\[ \boxed{E \text{ has the higher clustering coefficient.}} \]

6. Question (iii)

According to triadic closure, which new edge is most likely to be present?

这一问考的是 triadic closure 的经验规律。

核心思想是：

如果两个节点有很多共同朋友，那么它们将来更可能形成一条新边。

也就是优先看那些：

  • 当前没有边；
  • 但有较多共同邻居的点对。

6.1 枚举几个关键的非边

当前图中不存在的边包括：

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

我们比较它们的共同邻居数量。

非边 \(A\)--\(D\)

\[ N(A)=\{B,C,E,F\}, \quad N(D)=\{B,E,F\} \]

共同邻居：

\[ N(A) \cap N(D)=\{B,E,F\} \]

有 3 个共同邻居。

非边 \(B\)--\(E\)

\[ N(B)=\{A,C,D\}, \quad N(E)=\{A,D,F\} \]

共同邻居：

\[ \{A,D\} \]

有 2 个共同邻居。

非边 \(B\)--\(F\)

\[ N(B)=\{A,C,D\}, \quad N(F)=\{A,D,E\} \]

共同邻居：

\[ \{A,D\} \]

也有 2 个共同邻居。

非边 \(C\)--\(D\)

\[ N(C)=\{A,B\}, \quad N(D)=\{B,E,F\} \]

共同邻居：

\[ \{B\} \]

有 1 个共同邻居。

非边 \(C\)--\(E\)

\[ N(C)=\{A,B\}, \quad N(E)=\{A,D,F\} \]

共同邻居：

\[ \{A\} \]

有 1 个共同邻居。

非边 \(C\)--\(F\)

\[ N(C)=\{A,B\}, \quad N(F)=\{A,D,E\} \]

共同邻居：

\[ \{A\} \]

也有 1 个共同邻居。

6.2 结论

共同邻居最多的是：

\[ A \text{ and } D \]

因为它们有 3 个共同邻居 \(\{B,E,F\}\)，比其他候选点对都多。

而且加入边 \(AD\) 后，会同时闭合多个三角形：

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

所以根据 triadic closure，最可能新出现的边是：

\[ \boxed{(A,D)} \]

7. Question (iv)

What is the betweenness of edge \((B,D)\)?

这一问要求手算 edge betweenness。

7.1 定义

边 \(e\) 的 betweenness 是：

\[ \operatorname{betweenness}(e)=\sum_{s \neq t} \frac{\sigma_{st}(e)}{\sigma_{st}} \]

其中：

  • \(\sigma_{st}\)：节点 \(s\) 到 \(t\) 的最短路径条数；
  • \(\sigma_{st}(e)\)：这些最短路径里经过边 \(e\) 的条数。

对于无向图，通常按 无序点对 来算即可。

我们现在只算边：

\[ e=(B,D) \]

7.2 逐对检查哪些最短路径会经过 \((B,D)\)

图中节点有 6 个，所以无序点对一共有：

\[ \binom{6}{2}=15 \]

但并不是每一对都会贡献给边 \((B,D)\)，我们只看那些最短路径经过 \(BD\) 的点对。

Pair 1: \((A,D)\)

从 \(A\) 到 \(D\) 的最短路径长度为 2，有三条：

  1. \(A \to B \to D\)
  2. \(A \to E \to D\)
  3. \(A \to F \to D\)

其中只有一条经过边 \(BD\)。

所以这一对的贡献是：

\[ \frac{1}{3} \]

Pair 2: \((B,D)\)

\(B\) 和 \(D\) 本身就直接相连，唯一最短路径就是：

\[ B \to D \]

因此贡献是：

\[ 1 \]

Pair 3: \((B,E)\)

从 \(B\) 到 \(E\) 的最短路径长度为 2，有两条：

  1. \(B \to A \to E\)
  2. \(B \to D \to E\)

其中只有第二条经过 \(BD\)。

所以贡献是：

\[ \frac{1}{2} \]

Pair 4: \((B,F)\)

从 \(B\) 到 \(F\) 的最短路径长度为 2，也有两条：

  1. \(B \to A \to F\)
  2. \(B \to D \to F\)

其中只有第二条经过 \(BD\)。

所以贡献是：

\[ \frac{1}{2} \]

Pair 5: \((C,D)\)

从 \(C\) 到 \(D\) 的最短路径是：

\[ C \to B \to D \]

这是唯一长度为 2 的最短路径。

所以贡献是：

\[ 1 \]

7.3 其他点对为什么不贡献？

其他无序点对（如 \((A,B)\)、\((A,C)\)、\((E,F)\)、\((C,E)\) 等）要么：

  • 最短路径不经过 \(BD\)；
  • 要么即使存在经过 \(BD\) 的路径，也不是最短路径。

因此贡献为 0。

7.4 总和

把前面的贡献加起来：

\[ \operatorname{betweenness}(B,D) = \frac{1}{3}+1+\frac{1}{2}+\frac{1}{2}+1 \]

\[ = \frac{1}{3}+3 \]

\[ = \frac{10}{3} \]

所以边 \((B,D)\) 的 betweenness 为：

\[ \boxed{\frac{10}{3}} \]

8. 四个小问的最终答案

(i) Neighborhood overlap of \((A,B)\)

\[ \boxed{\frac{1}{4}} \]

(ii) Which one has higher clustering coefficient, \(D\) or \(E\)?

\[ \boxed{E} \]

并且：

\[ C(D)=\frac{1}{3}, \qquad C(E)=\frac{2}{3} \]

(iii) Most likely new edge according to triadic closure

\[ \boxed{(A,D)} \]

(iv) Betweenness of edge \((B,D)\)

\[ \boxed{\frac{10}{3}} \]

9. Python 验证（纯 Python 版本）

下面给一个不依赖额外库的验证版本。你可以用它检查 overlap、clustering coefficient 和 edge betweenness。

from collections import defaultdict, deque
from itertools import combinations

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

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

# (i) neighborhood overlap of (A, B)
NA = G['A'] - {'B'}
NB = G['B'] - {'A'}
overlap = len(NA & NB) / len(NA | NB)
print('overlap(A,B) =', overlap)

# (ii) clustering coefficient
for u in ['D', 'E']:
    nbrs = list(G[u])
    possible = len(nbrs) * (len(nbrs) - 1) / 2
    actual = 0
    for x, y in combinations(nbrs, 2):
        if y in G[x]:
            actual += 1
    print(f'C({u}) =', actual / possible)

# shortest paths for edge betweenness

def all_shortest_paths(G, 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])))
        else:
            for p in parents[x]:
                backtrack(p, path + [x])

    backtrack(t, [])
    return paths


def uses_edge(path, a, b):
    for i in range(len(path) - 1):
        if {path[i], path[i+1]} == {a, b}:
            return True
    return False

bet = 0
for i, s in enumerate(nodes):
    for t in nodes[i+1:]:
        paths = all_shortest_paths(G, s, t)
        cnt = sum(uses_edge(path, 'B', 'D') for path in paths)
        bet += cnt / len(paths)

print('edge betweenness(B,D) =', bet)

预期输出：

overlap(A,B) = 0.25
C(D) = 0.3333333333333333
C(E) = 0.6666666666666666
edge betweenness(B,D) = 3.3333333333333335

也就是：

\[ \frac{1}{4},\quad \frac{1}{3},\quad \frac{2}{3},\quad \frac{10}{3} \]

10. 这题最容易错的地方

错误 1：Neighborhood overlap 的分母算错

很多人会把分母写成 \(|N(A) \cup N(B)|\)，但要先把端点彼此去掉，也就是：

\[ N(A)\setminus\{B\}, \quad N(B)\setminus\{A\} \]

否则会把 \(A\) 或 \(B\) 自己也算进去。

错误 2：Clustering coefficient 忘了数“邻居之间”的边

不是数节点本身连出的边，而是数 邻居彼此之间 的边。

错误 3：Triadic closure 只凭感觉选边

最好明确比较“共同邻居数”，这样最稳。

错误 4：Edge betweenness 把所有经过该边的路径都算进去

只能算 最短路径。

不是最短的路径，一律不计入 betweenness。

COMP5313

Task 3 — Structural Balance

题目

Figure 3(a) 和 Figure 3(b) 给出了两个带正负号的社交网络。题目要求用 lecture 中讲的 two-step approach 判断这两个 signed network 是否 balanced。

先理解 balanced 到底是什么意思

这里边上的符号表示：

  • \(+\)：正关系
  • \(-\)：负关系

lecture 里的核心结论是：

一个 signed graph 是 balanced，当且仅当它的节点可以分成两个阵营，使得：

  • 阵营内部全是正边；
  • 阵营之间全是负边。

所以做题时，本质上就是检查：

这张图能不能被一致地分成两组？

如果可以，就是 balanced；如果中途推出矛盾，就是 not balanced。

two-step approach 做题时怎么落地

lecture 里的正式版本会先看 positive edges、再压成 supernodes；但手算时更直观的等价写法是：

  1. 任选一个点放进阵营 \(X\)；
  2. 遇到正边，就把另一端放进同一阵营；
  3. 遇到负边，就把另一端放进另一阵营；
  4. 一直沿着图往外推；
  5. 如果某个节点被同时要求属于两个不同阵营，就说明图不 balanced。

你可以把它记成三句话：

  • 正边：同组
  • 负边：异组
  • 推出矛盾：not balanced

Figure 3(a)

先把图上的关键边看清楚。Figure 3(a) 里我们会用到这些边：

  • \(IA\) 是负边
  • \(IG\) 是负边
  • \(GH\) 是负边
  • \(HF\) 是负边
  • \(FG\) 是正边
  • \(HE\) 是正边
  • \(FE\) 是负边
  • \(AB\) 是负边
  • \(BE\) 是负边
  • \(BC\) 是负边
  • \(BD\) 是负边
  • \(CD\) 是正边

现在开始分组。设

\[ A \in X \]

第一步：由 \(A\) 往外推

因为 \(IA\) 是负边，所以

\[ I \in Y \]

因为 \(AB\) 是负边，所以

\[ B \in Y \]

第二步：继续由 \(I\) 和 \(B\) 往外推

因为 \(IG\) 是负边，而 \(I \in Y\)，所以

\[ G \in X \]

因为 \(BE\) 是负边，而 \(B \in Y\)，所以

\[ E \in X \]

因为 \(BC\) 是负边，而 \(B \in Y\)，所以

\[ C \in X \]

因为 \(BD\) 是负边，而 \(B \in Y\)，所以

\[ D \in X \]

第三步：检查其他边是否一致

因为 \(CD\) 是正边，正边要求同组；而我们已经推出

\[ C \in X, \quad D \in X \]

这一步是一致的，没有问题。

因为 \(GH\) 是负边，而 \(G \in X\)，所以

\[ H \in Y \]

因为 \(HE\) 是正边，正边要求同组；而 \(E \in X\)，所以这条边要求

\[ H \in X \]

这就和上一步矛盾了：

\[ H \in Y \quad \text{and} \quad H \in X \]

也就是说：

  • 由负边 \(GH\) 推出 \(H\) 必须和 \(G\) 异组；
  • 由正边 \(HE\) 又推出 \(H\) 必须和 \(E\) 同组；
  • 但前面已经有 \(G \in X\) 且 \(E \in X\)，所以这两个要求互相冲突。

因此 Figure 3(a) 不能被一致地分成两个阵营，所以：

\[ \boxed{\text{Figure 3(a) is not balanced.}} \]

Figure 3(b)

Figure 3(b) 的关键边是：

  • \(IA\) 是负边
  • \(IG\) 是负边
  • \(GH\) 是正边
  • \(HF\) 是正边
  • \(FG\) 是正边
  • \(FE\) 是负边
  • \(AB\) 是正边
  • \(BE\) 是正边
  • \(BC\) 是正边
  • \(BD\) 是正边
  • \(CD\) 是负边

同样从

\[ A \in X \]

开始。

第一步：由 \(A\) 往外推

因为 \(IA\) 是负边，所以

\[ I \in Y \]

因为 \(AB\) 是正边，所以

\[ B \in X \]

第二步：继续往外推

因为 \(IG\) 是负边，而 \(I \in Y\)，所以

\[ G \in X \]

因为 \(GH\) 是正边，而 \(G \in X\)，所以

\[ H \in X \]

因为 \(HF\) 是正边，而 \(H \in X\)，所以

\[ F \in X \]

因为 \(FE\) 是负边，而 \(F \in X\)，所以

\[ E \in Y \]

另一方面，因为 \(BE\) 是正边，而 \(B \in X\)，所以又必须有

\[ E \in X \]

这就产生了直接矛盾：

\[ E \in Y \quad \text{and} \quad E \in X \]

也就是说：

  • 左边这部分通过 \(G\)-\(H\)-\(F\)-\(E\) 推下来，要求 \(E\) 与 \(F\) 异组，所以 \(E \in Y\)；
  • 右边通过正边 \(AB\) 和 \(BE\) 推下来，又要求 \(E\) 与 \(B\) 同组，所以 \(E \in X\)。

两个要求不能同时成立，因此 Figure 3(b) 也不能被一致地分成两个阵营。

所以：

\[ \boxed{\text{Figure 3(b) is not balanced.}} \]

最终答案

  • Figure 3(a): not balanced
  • Figure 3(b): not balanced

即：

\[ \boxed{\text{Both Figure 3(a) and Figure 3(b) are not balanced.}} \]

COMP5313

Task 4 — Network Bottlenecks

题目

题目给出一张 Sydney highway map，并且 NSW Roads Minister 提出 claim：

The new WestConnex project will reduce traffic congestion in the Sydney area.

在“所有点对之间交通需求均匀”的假设下，需要回答三件事：

  1. 应该计算什么图性质来衡量 bottleneck；
  2. 如果加入边 \(\langle \text{Strathfield}, \text{Airport} \rangle\)（WestConnex），应如何验证 bottleneck 是否下降；
  3. 这个 claim 最终应判为 true 还是 false，并解释原因。

这一题的核心非常明确：

  • 题目说 traffic is uniform between all pairs of nodes；
  • 这正对应 lecture 里用 betweenness 来近似流量压力；
  • 因为这里关注的是“哪一段 highway 更像 bottleneck”，所以重点是 edge betweenness，不是 node betweenness。

1. 题目在考什么

如果每一对节点之间都等概率地产生交通需求，那么：

  • 一条边出现在越多最短路径上，
  • 它承受的潜在交通压力就越大，
  • 它越像 bottleneck。

因此本题要计算的量是：

\[ \boxed{\text{edge betweenness centrality}} \]

2. Figure 4 的图抽象

把 Figure 4 抽象成 lecture 里的 graph，可以把主要节点看成：

  • Dean Park
  • M2
  • North Sydney
  • M1
  • Airport
  • M5
  • M7（south）
  • Eastern Creek
  • M7（north）
  • M4
  • Strathfield

在不加入 WestConnex 前，可把主要连接关系写成：

  • Dean Park -- M2
  • Dean Park -- M7 (north)
  • M7 (north) -- Eastern Creek
  • Eastern Creek -- M4
  • Eastern Creek -- M7 (south)
  • M4 -- Strathfield
  • M2 -- North Sydney
  • North Sydney -- M1
  • Strathfield -- M1
  • M1 -- Airport
  • Airport -- M5
  • M5 -- M7 (south)

而题目说新建的 WestConnex 是：

\[ \langle \text{Strathfield}, \text{Airport} \rangle \]

也就是在原图上新增一条边：

  • Strathfield -- Airport

3. 路网重构图

graph TD
    DP[Dean Park]
    M2[M2]
    NS[North Sydney]
    M1[M1]
    AP[Airport]
    M5[M5]
    M7S[M7 south]
    EC[Eastern Creek]
    M7N[M7 north]
    M4[M4]
    ST[Strathfield]

    DP --- M2
    DP --- M7N
    M7N --- EC
    EC --- M4
    EC --- M7S
    M4 --- ST
    M2 --- NS
    NS --- M1
    ST --- M1
    M1 --- AP
    AP --- M5
    M5 --- M7S

加上 WestConnex 后，只是多一条：

graph TD
    DP[Dean Park]
    M2[M2]
    NS[North Sydney]
    M1[M1]
    AP[Airport]
    M5[M5]
    M7S[M7 south]
    EC[Eastern Creek]
    M7N[M7 north]
    M4[M4]
    ST[Strathfield]

    DP --- M2
    DP --- M7N
    M7N --- EC
    EC --- M4
    EC --- M7S
    M4 --- ST
    M2 --- NS
    NS --- M1
    ST --- M1
    M1 --- AP
    AP --- M5
    M5 --- M7S
    ST ---|WestConnex| AP

4. Question (i)

Assume that traffic is uniform between all pairs of nodes. What property should we compute? Does it apply to nodes or edges?

应该计算的是：

\[ \boxed{\text{edge betweenness centrality}} \]

原因是：

  • uniform all-pairs traffic 意味着每对节点之间都有潜在最短路径流量；
  • bottleneck 反映的是“哪条 link 被大量 shortest paths 经过”；
  • 所以这里关注的是 link / edge，不是 vertex。

(i) 的答案

  • Property: edge betweenness centrality
  • It applies to: edges (links)

5. Question (ii)

Your task is now to verify whether traffic bottlenecks will be reduced after WestConnex is created. How do you proceed?

流程就是两步：

Step 1: 在原图上计算所有 edge betweenness

对 Figure 4 原始路网的每一条边，计算：

\[ \operatorname{betweenness}(e) = \sum_{s<t} \frac{\sigma_{st}(e)}{\sigma_{st}} \]

其中：

  • \(\sigma_{st}\) 是 \(s\) 到 \(t\) 的最短路径条数；
  • \(\sigma_{st}(e)\) 是这些最短路径中经过边 \(e\) 的条数。

Step 2: 加入 WestConnex 后重新计算

把新边

\[ (\text{Strathfield}, \text{Airport}) \]

加进图中，再计算一次所有 edge betweenness。

Step 3: 比较前后结果

重点看两类变化：

  1. 最大 bottleneck 是否下降；
  2. 原本高 betweenness 的关键边是否明显减压。

如果只是某几条边下降，但最严重 bottleneck 没变，那么不能简单说“Sydney area 的 congestion 被整体缓解”。

6. Before / After 的比较

在上面的图抽象下，计算 edge betweenness 后，可以看到：

加边之前，较大的 bottleneck 在：

  • Eastern Creek -- M7 (north)
  • M1 -- North Sydney
  • Airport -- M1
  • Eastern Creek -- M7 (south)
  • M1 -- Strathfield

其中最高的一组大约是：

\[ 14 \]

加入 WestConnex 之后

新增边 Strathfield -- Airport 会吸走一部分原本必须经过

  • Strathfield -- M1
  • M1 -- Airport

的最短路径流量。

所以这些边的 betweenness 会下降，例如：

  • \(\text{Strathfield} - \text{M1}\)：下降
  • \(\text{M1} - \text{Airport}\)：下降
  • \(\text{M5}\) 一侧的一部分压力也会下降

但是，最高 bottleneck 并没有整体消失。

像下面这些边仍然非常高：

  • Eastern Creek -- M7 (north)
  • M1 -- North Sydney

也就是说，WestConnex 主要缓解的是 Strathfield 到 Airport 之间的 east-west 连接压力，但并没有把整个网络最严重的 bottleneck 都降下来。

7. Question (iii)

Is the claim true or false?

题目原话是：

The new WestConnex project will reduce traffic congestion in the Sydney area.

如果按照本题的 graph model 和 uniform all-pairs shortest-path traffic 来理解，这个说法 过于强。

更准确的结论是：

  • WestConnex 会降低部分边的 betweenness，尤其是原来依赖 Strathfield -- M1 -- Airport 这条通道的最短路径；
  • 但网络中的最大 bottleneck 不一定下降；
  • 有些最关键的高压边仍然保持很高的 betweenness。

因此，如果把“reduce traffic congestion in the Sydney area”理解成 整个 Sydney 网络层面的 bottleneck 都明显变小，那么这个 claim 应判为：

\[ \boxed{\text{False}} \]

因为它只是 局部缓解，不是 整体消除主要 bottleneck。

8. 更适合作业写法的结论

(i)

应该计算 edge betweenness centrality，它作用在 edges / links 上。

(ii)

做法是：

  1. 在原始路网上计算所有 edge betweenness；
  2. 加入边 \((\text{Strathfield}, \text{Airport})\)；
  3. 再次计算 edge betweenness；
  4. 比较 bottleneck edges 的数值是否下降，尤其看最大值是否下降。

(iii)

结论：

\[ \boxed{\text{The claim is false in this model.}} \]

原因是 WestConnex 确实会降低一部分局部边的 betweenness，但不会把整个网络里最严重的 bottleneck 都降下来，所以不能直接说 Sydney area 的 congestion 整体被有效降低。

9. Python 验证代码

import networkx as nx

# ---------- Build the graph ----------
edges_before = [
    ('Dean Park', 'M2'),
    ('Dean Park', 'M7 North'),
    ('M7 North', 'Eastern Creek'),
    ('Eastern Creek', 'M4'),
    ('Eastern Creek', 'M7 South'),
    ('M4', 'Strathfield'),
    ('M2', 'North Sydney'),
    ('North Sydney', 'M1'),
    ('Strathfield', 'M1'),
    ('M1', 'Airport'),
    ('Airport', 'M5'),
    ('M5', 'M7 South'),
]

westconnex = ('Strathfield', 'Airport')

G_before = nx.Graph()
G_before.add_edges_from(edges_before)

G_after = G_before.copy()
G_after.add_edge(*westconnex)

# ---------- Compute edge betweenness ----------
before_bc = nx.edge_betweenness_centrality(G_before, normalized=False)
after_bc = nx.edge_betweenness_centrality(G_after, normalized=False)

# ---------- Sort and print ----------
def print_scores(title, scores):
    print(title)
    for edge, value in sorted(scores.items(), key=lambda x: (-x[1], x[0])):
        print(f"{edge}: {value}")
    print()

print_scores("Before WestConnex:", before_bc)
print_scores("After WestConnex:", after_bc)

# ---------- Compare changes ----------
all_edges = sorted(set(before_bc) | set(after_bc))
print("Changes (after - before):")
for edge in all_edges:
    before = before_bc.get(edge, 0)
    after = after_bc.get(edge, 0)
    diff = after - before
    print(f"{edge}: before={before}, after={after}, change={diff}")

10. 这题最容易错的地方

错误 1：把 bottleneck 理解成 node centrality

这里讨论的是 highway links，所以要看的是 edge betweenness。

错误 2：只看新增边本身变得很有用，就说 claim 为真

新增边有用，不代表 整体 bottleneck 一定下降。

错误 3：没有比较 before / after

这题不是单独算一次 centrality，而是必须比较：

  • 原图
  • 加 WestConnex 后的图

只有这样才能回答 “will be reduced” 这个动态问题。

COMP5313

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