COMP5313 Week 02 弱联系与结构平衡讲课总结

Posted on Edited on In Word count in article: 1k Reading time ≈ 4 mins.
COMP5313 Week 02 讲课总结，整理 small world、强弱联系、局部桥、STC、neighbourhood overlap、结构洞与 signed graph 结构平衡的考点重点。

COMP5313 Week 02 讲课总结：Weak Ties 与 Structural Balance

1. 本讲主题

本讲进入社交网络的局部结构。老师主要讲两条线：

  • Weak ties：弱联系为什么对信息扩散和找工作重要。
  • Structural balance：正负关系网络中，朋友和敌人的三角结构什么时候稳定。

2. Small World Phenomenon

老师回顾了 Milgram 的小世界实验：

  • 参与者不能直接寄给目标，只能转给自己认识的人。
  • 目标信息包括姓名、地址、职业等。
  • 到达的信件中，中位步数约为 6。

重点结论：

  • 大规模社交网络中存在很多短路径。
  • 人们只用局部信息，也可能协作找到短路径。
  • 这个思想后面 Week 10 的 decentralized search 会再次出现。

3. 强联系与弱联系

强联系：

  • 亲密、频繁互动的关系。
  • 常在同一个社交圈内部。

弱联系：

  • 较弱、较少互动的关系。
  • 更容易跨越不同圈子，带来新信息。

老师强调 Granovetter 的核心发现：找工作时，弱联系常比强联系更有用，因为弱联系连接不同社群。

4. Bridge 与 Local Bridge

Bridge：

  • 删除这条边后，图中两个端点不再连通。
  • 真实大型社交网络中很少见。

Local bridge：

  • 两个端点没有共同邻居。
  • 删除后，两个端点之间距离大于 2。

Span：

  • 删除 local bridge 后，两个端点之间的新最短路径长度。

做题时 local bridge 的关键判断是：两端点是否有共同邻居。

5. Strong Triadic Closure, STC

STC 性质：

如果节点 \(A\) 与 \(B\)、\(C\) 都是强联系，那么 \(B\) 和 \(C\) 至少应该有一条边。

老师重点证明：

若节点 \(A\) 满足 STC 且有至少两条强联系，则 \(A\) 的任何 local bridge 都必须是弱联系。

证明思路：

  1. 假设 \(A\)-\(B\) 是强 local bridge。
  2. \(A\) 还有另一条强联系 \(A\)-\(C\)。
  3. 由 STC，\(B\) 和 \(C\) 必须相连。
  4. 那么 \(A\)-\(B\) 两端点有共同邻居 \(C\)，不可能是 local bridge。
  5. 矛盾，所以 \(A\)-\(B\) 必须是弱联系。

这是高频证明题。

6. Neighbourhood Overlap 与 Embeddedness

Neighbourhood overlap：

[ O(A,B)= ]

含义：

  • 衡量一条边两端点的社交圈有多重叠。
  • local bridge 的 overlap 为 0。
  • overlap 越高，通常关系越强。

Embeddedness：

  • 一条边两端点的共同邻居数量。
  • 和 overlap 类似，都衡量边被局部结构包围的程度。

7. 结构洞

结构洞指两个群体之间缺少直接联系，而某个节点位于它们之间。

处在结构洞位置的节点有优势：

  • 能把不同圈子的非冗余信息连接起来。
  • 能控制信息流通。
  • 在组织或职业网络中具有 brokerage / gatekeeper 作用。

8. Signed Graph 与结构平衡

Signed graph 中每条边有正负号：

  • 正边：朋友、合作、支持。
  • 负边：敌人、冲突、不信任。

三角形平衡规则：

三角形 是否平衡 直觉
3 条正边 平衡 我的朋友的朋友也是朋友
1 正 2 负 平衡 共同敌人促成朋友
2 正 1 负 不平衡 两个朋友之间出现敌对
3 条负边 不平衡 敌人的敌人不一定继续敌对

等价记忆：平衡三角形含偶数条负边。

9. 完全图 Balance Theorem

完全 signed graph balanced 当且仅当：

  • 所有边都是正边；或
  • 节点能分成两组，组内全正，组间全负。

证明思路：

  1. 若存在负边，选一个基点 \(A\)。
  2. 把 \(A\) 的朋友放入 \(X\)，敌人放入 \(Y\)。
  3. 用平衡三角形推出 \(X\) 内全正，\(Y\) 内全正，\(X\) 与 \(Y\) 之间全负。
  4. 反方向则直接检查任意三角形，只会出现 3 正或 1 正 2 负。

10. 考点重点

  • 会解释 small world 和六度分隔。
  • 会区分 strong tie、weak tie、bridge、local bridge。
  • 会计算 neighbourhood overlap。
  • 必会 STC 推出 local bridge 为弱联系的反证法。
  • 会解释 weak ties 为什么带来新信息。
  • 会判断 signed triangle 是否 balanced。
  • 会复述完全图 Balance Theorem 的两组划分结论和证明思路。