COMP5313 Assignment 1 题解（二）

Posted on Edited on In Word count in article: 2.6k Reading time ≈ 10 mins.
根据 Figure 2 的社交网络，回答四个问题：

COMP5313 Assignment 1 题解（二）

Task 2 — Link Formation

题目

根据 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