COMP5313 Assignment 1 题解（一）

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