COMP5313 Assignment 1 题解 04 - Network Bottlenecks

COMP5313 Assignment 1 题解（四）

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. 如果加入边 （WestConnex），应如何验证 bottleneck 是否下降；
3. 这个 claim 最终应判为 true 还是 false，并解释原因。

这一题的核心非常明确：

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

---

1. 题目在考什么

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

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

因此本题要计算的量是：

---

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 是：

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

• 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?

应该计算的是：

原因是：

• 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 原始路网的每一条边，计算：

其中：

• 是 到 的最短路径条数；
• 是这些最短路径中经过边 的条数。

Step 2: 加入 WestConnex 后重新计算

把新边

加进图中，再计算一次所有 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

其中最高的一组大约是：

---

加入 WestConnex 之后

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

• Strathfield -- M1
• M1 -- Airport

的最短路径流量。

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

• ：下降
• ：下降
• 一侧的一部分压力也会下降

但是，最高 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 应判为：

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

---

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

(i)

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

(ii)

做法是：

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

(iii)

结论：

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

---

9. Python 验证代码

from collections import defaultdict, deque

nodes = [
    'Dean Park', 'M2', 'North Sydney', 'M1', 'Airport',
    'M5', 'M7 South', 'Eastern Creek', 'M7 North',
    'M4', 'Strathfield'
]

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'),
]

edges_after = edges_before + [('Strathfield', 'Airport')]


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

    scores = 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])))
                    scores[e] += 1 / len(paths)

    return dict(scores)

before = edge_betweenness(nodes, edges_before)
after = edge_betweenness(nodes, edges_after)

print('Before:')
for e, v in sorted(before.items(), key=lambda x: -x[1]):
    print(e, v)

print('\nAfter:')
for e, v in sorted(after.items(), key=lambda x: -x[1]):
    print(e, v)

---

10. 这题最容易错的地方

错误 1：把 bottleneck 理解成 node centrality

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

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

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

错误 3：没有比较 before / after

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

• 原图
• 加 WestConnex 后的图

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