COMP5313 Assignment 1 题解 02 - Link Formation

COMP5313 Assignment 1 题解（二）

Task 2 — Link Formation

题目

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

1. 边 的 neighborhood overlap 是多少；
2. 节点 和 中，谁的 clustering coefficient 更高；
3. 如果将来网络继续演化，根据 triadic closure，哪一条新边最可能出现；
4. 边 的 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 的图结构

根据题图，节点为：

边为：

• --
• --
• --
• --
• --
• --
• --
• --
• --

因此：

---

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

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

• 左上角有三角形 --
• 左侧还有三角形 --
• 节点 连向

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

---

3. 各节点邻居集合

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

---

4. Question (i)

What is the neighborhood overlap of edge ?

4.1 定义

这一问其实就是在算：

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

Neighborhood overlap 可以写成：

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

这里：

• 表示节点 的邻居集合；
• 表示把对方节点先去掉；
• 分子是共同邻居；
• 分母是两边邻居合起来以后去重的总数。

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

---

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

对于边 ：

共同邻居是：

所以分子为：

并集是：

所以分母为：

---

4.3 得到 overlap

因此：

---

4.4 答案

---

5. Question (ii)

Between nodes and , which one has a higher clustering coefficient?

5.1 定义

Clustering coefficient 看的是：

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

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

公式写成：

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

条边。

所以也可以写成：

你可以把它理解成：

---

5.2 计算 的 clustering coefficient

的邻居是：

所以 ，最大可能边数为：

现在检查 之间有哪些边：

• --：不存在
• --：不存在
• --：存在

所以实际存在的边数是：

因此：

---

5.3 计算 的 clustering coefficient

的邻居是：

所以 ，最大可能边数也是：

检查 之间有哪些边：

• --：不存在
• --：存在
• --：存在

所以实际存在的边数是：

因此：

---

5.4 比较

因为：

所以：

---

6. Question (iii)

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

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

核心思想是：

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

也就是优先看那些：

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

---

6.1 枚举几个关键的非边

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

• --
• --
• --
• --
• --
• --

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

---

非边 --

共同邻居：

有 3 个共同邻居。

---

非边 --

共同邻居：

有 2 个共同邻居。

---

非边 --

共同邻居：

也有 2 个共同邻居。

---

非边 --

共同邻居：

有 1 个共同邻居。

---

非边 --

共同邻居：

有 1 个共同邻居。

---

非边 --

共同邻居：

也有 1 个共同邻居。

---

6.2 结论

这一问的核心概念是 triadic closure，意思是：

如果两个人已经有不少共同朋友，那么他们以后更容易直接建立联系。

因此做法很直接：

• 先找出图里还不存在的边；
• 再比较这些 non-edges 各自有多少共同邻居；
• 共同邻居越多，越可能在未来形成新边。

这里共同邻居最多的是：

因为它们有 3 个共同邻居 ，比其他候选点对都多。

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

• --
• --
• --

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

---

7. Question (iv)

What is the betweenness of edge ?

这一问要求手算 edge betweenness。

7.1 定义

你可以先把 edge betweenness 理解成：

一条边到底有多“关键”，有多少组点之间的最短路会经过它。

如果一条边经常出现在很多最短路径上，它就更像整张图里的“交通要道”。

正式定义为：

其中：

• ：节点 到 的最短路径总数；
• ：这些最短路径里，经过边 的条数。

所以这整个式子的意思其实就是：

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

我们现在只算边：

---

7.2 逐对检查哪些最短路径会经过

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

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

---

Pair 1:

从 到 的最短路径长度为 2，有三条：

其中只有一条经过边 。

所以这一对的贡献是：

---

Pair 2:

和 本身就直接相连，唯一最短路径就是：

因此贡献是：

---

Pair 3:

从 到 的最短路径长度为 2，有两条：

其中只有第二条经过 。

所以贡献是：

---

Pair 4:

从 到 的最短路径长度为 2，也有两条：

其中只有第二条经过 。

所以贡献是：

---

Pair 5:

从 到 的最短路径是：

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

所以贡献是：

---

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

其他无序点对（如 、、、 等）要么：

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

因此贡献为 0。

---

7.4 总和

把前面的贡献加起来：

所以边 的 betweenness 为：

---

8. 四个小问的最终答案

(i) Neighborhood overlap of

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

并且：

(iii) Most likely new edge according to triadic closure

(iv) Betweenness of edge

---

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

也就是：

---

10. 这题最容易错的地方

错误 1：Neighborhood overlap 的分母算错

很多人会把分母写成 ，但要先把端点彼此去掉，也就是：

否则会把 或 自己也算进去。

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

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

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

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

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

只能算 最短路径。

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