COMP5313 Week 03 结构平衡与同质性讲课总结
COMP5313 Week 03 讲课总结：Structural Balance 续与 Homophily
1. 本讲主题
本讲先把 Week 02 的结构平衡扩展到不完全图，然后转到网络形成机制：
- 不完全 signed graph 如何判断 balanced。
- Homophily 如何检测。
- 关系形成中的 triadic / focal / membership closure。
- Schelling 模型如何说明局部偏好会产生整体隔离。
2. 不完全图的 Structural Balance
不完全 signed graph 不是所有节点对都有边。
老师给了两个等价视角：
- 能否补全缺失边，使它成为 balanced 完全图。
- 能否把节点分成两组，使已有正边都在组内，已有负边都跨组。
如果可以做到，就是 balanced。
3. 奇数负边环定理
关键结论：
signed graph 不平衡，当且仅当存在一个含奇数条负边的环。
直觉：
- 沿正边要求“同组”。
- 沿负边要求“异组”。
- 一个环中负边数量为奇数时，绕一圈回来会要求同一个节点既在同组又在异组，产生矛盾。
4. 两步法检验 Balance
老师讲了一个实用两步法。
Step 1：只看正边
先用正边找 connected components，把每个正边连通分量缩成 supernode。
如果某个 supernode 内部存在负边：
- 说明有一条由正边组成的路径，加上一条负边。
- 形成只含 1 条负边的环。
- 直接 unbalanced。
Step 2：只看 supernodes 之间的负边
缩点后，图中只剩负边。
判断这个图是否 bipartite：
- 如果是二部图，balanced。
- 如果存在奇数环，unbalanced。
BFS 可以用来判断二部图。
5. 直接 BFS / DFS 分组法
也可以不显式缩点，直接做二色分组：
- 遇到正边：两端点必须同组。
- 遇到负边：两端点必须异组。
- 如果产生矛盾，则 unbalanced。
- 如果能给所有节点一致分组，则 balanced。
这是做题时最直接的方法。
6. Homophily 同质性
Homophily：
相似的人更倾向于连接在一起。
检测方法：
假设群体 A 占比 \(p\)，群体 B 占比 \(q=1-p\)。如果边随机形成，则跨组边比例期望为：
[ 2pq ]
如果真实跨组边比例显著低于 \(2pq\)，说明存在 homophily。
7. Selection 与 Social Influence
老师强调 homophily 的两个来源：
- Selection：人们主动选择和相似的人建立关系。
- Social influence：朋友之间互相影响，逐渐变得相似。
做概念题时要区分：
- 先相似后连边，是 selection。
- 先连边后变相似，是 social influence。
8. Affiliation Network
Affiliation network 通常是二部图：
- 一类节点是人。
- 一类节点是活动、组织、课程、公司等。
- 边表示某个人参加某活动。
它可以和普通社交网络一起分析，用来解释关系形成。
9. 三种闭包机制
Triadic Closure
共同朋友越多，未来成为朋友的概率越高。
这是 selection，因为人选择和朋友的朋友建立关系。
Focal Closure
共同活动 / 共同组织越多，未来成为朋友的概率越高。
也是 selection，因为共同焦点带来接触机会。
Membership Closure
如果朋友参加某活动，自己之后也更可能加入该活动。
这是 social influence，因为已有社交关系影响个人行为。
10. Clustering Coefficient
节点 \(v\) 的 clustering coefficient：
[ C(v)= = ]
Triadic closure 会提高 clustering coefficient。
11. Schelling Segregation Model
模型设定：
- 网格上有两类 agent。
- 每个 agent 看周围邻居。
- 如果同类邻居数量低于阈值，就搬家。
老师强调的结论：
- 即使个人只要求轻微偏好，也可能导致整体上高度隔离。
- 局部规则可以产生宏观模式。
12. 考点重点
- 会用“奇数条负边环”判断 signed graph 是否 unbalanced。
- 会用两步法或 BFS/DFS 分组法检验 balance。
- 会解释 homophily，并用 \(2pq\) 做随机基准比较。
- 会区分 selection 和 social influence。
- 会解释 triadic closure、focal closure、membership closure。
- 会计算 clustering coefficient。
- 会说明 Schelling 模型的核心结论：局部偏好导致全局 segregation。