COMP5313 Lecture 02b Summary - Structural Balance

Lecture 02b — Structural Balance

主题

这节讲 signed graph 和 structural balance。

1. Signed graph

图中每条边带符号： - 表示友好/支持/联盟 - 表示敌对/冲突/对立

2. 三角形层面的 balance

对于三角形： - 三条正边：balanced - 一条正边 + 两条负边：balanced - 两条正边 + 一条负边：unbalanced - 三条负边：unbalanced

记忆方式

balanced triangle 等价于： - 正边数为 1 或 3 - 负边数为 0 或 2

3. 为什么会有不平衡

不平衡三角形表示社会张力： - “我的两个朋友互相敌对” - “三个人互相敌对” 都会诱发结构变化

4. 完全图上的 structural balance

一个 complete signed graph balanced，当且仅当其每个三角形都 balanced。

5. 两阵营刻画

更强的全局结论：

一个 signed complete graph balanced，当且仅当它的节点可以分成两个阵营： - 阵营内部全是正边 - 阵营之间全是负边

6. 题目常用 two-step approach

Step 1

任选一个节点放进阵营 。

Step 2

• 正边两端放同一阵营
• 负边两端放不同阵营

如果推导到最后没有冲突，则 balanced；如果出现矛盾，则 not balanced。

应用

• 国际关系
• 社交敌友关系
• 在线平台的支持/反对网络

takeaway

Structural balance 本质是在看：一个 signed network 能不能被解释成“两个阵营内部友好、阵营之间对立”。