COMP5313 Assignment 1 题解 01 - Strong and Weak Ties

Posted on 2026-03-26 Edited on 2026-03-30 In Course , COMP5313 Word count in article: 1.4k Reading time ≈ 5 mins.

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. 题目目标

题目要求：

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

2. STC 的直观理解

设某个节点是，它和两个邻居都是 strong ties。

那么 STC 要求：

这里的意思是：

和之间至少要有一条边；
这条边可以是 strong，也可以是 weak。

所以 STC 检查的是：

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

3. Figure 1 的图结构整理

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

节点集合为：

边集合为：

--: strong
--: strong
--: weak
--: weak
--: strong
--: weak
--: strong
--: weak

因此：

其中 strong edges 为：

weak edges 为：

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

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

和 没有直接边；
但同时和是 strong；
也同时和是 strong。

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

5. 解题策略

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

通用步骤

对于每个节点：

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

6. 逐点详细检查

6.1 Node

与相连的边有：

：strong
：strong
：weak

所以的 strong neighbors 是：

现在检查和之间是否有边。

观察图可知：

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

因此：

6.2 Node

与相连的边有：

：strong
：strong
：weak

所以的 strong neighbors 是：

检查和之间是否有边。

图中有：

并且它是 weak edge。

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

因此：

6.3 Node

与相连的边有：

：strong
：strong
：weak

所以的 strong neighbors 是：

检查和是否相连。

由于图中有 weak edge ，因此：

所以：

6.4 Node

与相连的边有：

：weak
：weak
：weak

所以 没有 strong tie。

也就是说：

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

所以：

6.5 Node

与相连的边有：

：strong
：strong
：weak
：weak

所以的 strong neighbors 是：

现在检查和之间是否有边。

图中没有这条边，因此：

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

所以：

7. 总结表格

Node	Strong neighbors	这些 strong neighbors 之间是否有边	是否满足 STC
		否	否
		是，存在	是
		是，存在	是
		不需要检查	是
		否	否

8. 最终答案

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

违反该性质的节点是：

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。

所以像虽然是 weak，但它依然足以让：

满足 STC；
满足 STC。

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

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

weak ties 不会触发 STC 检查。

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

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

12. 一句话记忆

这题可以记成一句话：

谁同时通过 strong tie 连到和，而又没边，谁就违反 STC。

在这张图里，正好就是：