COMP5313 - Chapter 5 Positive and Negative Relationships 正面与负面关系

Posted on In Word count in article: 6.7k Reading time ≈ 24 mins.
讲解结构平衡、弱结构平衡及其在网络中的应用

Chapter 5: Positive and Negative Relationships（正面与负面关系）

教材：Networks, Crowds, and Markets: Reasoning about a Highly Connected World 作者：David Easley & Jon Kleinberg, Cambridge University Press, 2010

一、结构平衡基础理论（Section 5.1: Structural Balance）

1.1 正负边概念与基本设定

网络中的关系可分为两类： - 正边（Positive Edge，记为 +）：表示友谊、联盟、信任等正面关系 - 负边（Negative Edge，记为 -）：表示敌对、对抗、不信任等负面关系

本章研究的核心设定是完全图（Complete Graph，Clique），即任意两个节点之间都存在一条被标记为 + 或 - 的边。这种图在现实应用中代表： - 国际关系中所有国家对之间的联盟/对立状态 - 在线社区中用户之间的信任/不信任关系 - 社团组织中的内部派系关系

1.2 三角形的四种配置及平衡性分析

对于任意三个节点（三角形）A、B、C，其三条边的标记方式有四种：

配置(a) 三条边均为正（+） - 关系描述：A与B友好，B与C友好，A与C也友好 - 平衡性：平衡的（Balanced） - 心理学解释：三人互为朋友，彼此信任，系统稳定 - 能量状态：最低能量状态，无调和压力

配置(b) 两条正边，一条负边 - 关系描述：假设边A-B为 +，A-C为 +，B-C为 - - 平衡性：不平衡的（Unbalanced） - 心理学解释：A既与B友好又与C友好，但B与C是敌人。这产生压力（称为平衡压力 / Balance Pressure） - 压力机制：根据平衡心理学（Balance Psychology），A会倾向于： - 要么改变A-B或A-C的关系（从 + 变为 -） - 要么调和B与C的冲突，使B-C从 - 变为 + - 这是最容易导致关系变化的配置

配置(c) 一条正边，两条负边 - 关系描述：假设边A-B为 +，A-C为 -，B-C为 - - 平衡性：平衡的（Balanced） - 心理学解释："敌人的敌人是朋友"（Enemy of my enemy is my friend） - 现实场景：A与B结成同盟共同对抗C（第三方敌人） - 能量状态：稳定配置，双方有共同利益（对抗共同敌人）

配置(d) 三条边均为负（-） - 关系描述：A、B、C三人相互敌对 - 平衡性：不平衡的（Unbalanced） - 心理学解释：三角形冲突，极其不稳定 - 实际情况：这种情况在实际网络中极为罕见，因为不稳定的系统必然会导致联盟形成

1.3 平衡性判断规则

关键规则：三角形平衡性取决于正边的数量

\[\text{平衡三角形} \Leftrightarrow \text{正边数量为 1 或 3}\]

\[\text{不平衡三角形} \Leftrightarrow \text{正边数量为 0 或 2}\]

数学证明直观理解：

令 \(s\) 为三角形中正边的数量： - \(s = 3\)：配置(a)，三人互为朋友 ✓ 平衡 - \(s = 2\)：配置(b)，两条同盟，一条敌对 ✗ 不平衡 - \(s = 1\)：配置(c)，一个同盟联合对抗敌人 ✓ 平衡 - \(s = 0\)：配置(d)，三人相互敌对 ✗ 不平衡

1.4 结构平衡属性的正式定义

结构平衡属性（Structural Balance Property）

对于标记完全图，若满足以下条件，则称其满足结构平衡属性：

对于任意三个节点的集合，这三条边中要么所有边都标记为 +，要么恰有一条边标记为 +

数学表述：设图 \(G = (V, E)\)，标记函数为 \(\sigma: E \to \{+, -\}\)，则图 \(G\) 平衡当且仅当：

\[\forall \{u, v, w\} \subset V, |\{e \in E(\{u,v,w\}): \sigma(e) = + \}| \in \{1, 3\}\]

其中 \(E(\{u,v,w\})\) 表示这三个节点之间的三条边。

二、平衡网络的结构特征化（Section 5.2: Characterizing Balanced Networks）

2.1 实现平衡的两种基本方式

在结构平衡约束下，完全图只能呈现两种极端的结构：

方式一：全球一致（Global Consensus） - 所有节点间的边都标记为 + - 对应现实含义：全网络的完全统一，所有人互为朋友 - 数学表示：\(\sigma(e) = +, \forall e \in E\)

方式二：二部划分（Bipartite Division） - 将节点集分为两个不相交的组：\(V = X \cup Y\)，\(X \cap Y = \emptyset\) - 组内关系：\(X\) 内的任意两个节点间为 +，\(Y\) 内的任意两个节点间为 + - 组间关系：任何 \(X\) 中的节点与 \(Y\) 中的节点间为 - - 现实含义：形成两个相互敌对的联盟或阵营

2.2 Harary 平衡定理（1953）

定理表述（Harary's Balance Theorem）

如果一个标记完全图满足结构平衡属性，则必然满足以下两个条件之一：

(a) 所有节点对均为朋友： 存在 \(\sigma(e) = +\) 对所有 \(e \in E\)

(b) 二部平衡结构： 存在节点的二部划分 \(V = X \cup Y\) 使得： - \(\forall u, v \in X\)：\(\sigma(\{u, v\}) = +\) - \(\forall u, v \in Y\)：\(\sigma(\{u, v\}) = +\) - \(\forall u \in X, v \in Y\)：\(\sigma(\{u, v\}) = -\)

定理的重要意义

这个定理建立了局部属性和全局结构之间的深刻联系： - 局部属性：每个三角形都满足平衡条件（1或3条正边） - 全局结构：整个网络要么是单一阵营，要么是两个相互对立的阵营

这说明仅从三角形层面的局部约束就可以推断出整个网络的宏观结构！

2.3 Harary 定理的严格证明

证明过程：

第一步：选择任意基准节点

选择任意节点 \(A \in V\)。定义两个集合： - \(X = \{A\} \cup \{B \in V : \sigma(\{A, B\}) = +\}\) （\(A\) 及其所有朋友） - \(Y = \{C \in V : \sigma(\{A, C\}) = -\}\) （\(A\) 的所有敌人）

显然 \(X \cap Y = \emptyset\)，\(X \cup Y = V\)（因为是完全图）。

第二步：情况一 - \(Y = \emptyset\) 时

若 \(Y\) 为空，则所有节点都是 \(A\) 的朋友：\(V = X\)。

需要证明：任意两个不同于 \(A\) 的节点 \(B, C \in X \setminus \{A\}\) 之间也是朋友。

反证法：假设存在 \(B, C \in X \setminus \{A\}\) 使得 \(\sigma(\{B, C\}) = -\)。

考虑三角形 \(\{A, B, C\}\)： - 边 \(\{A, B\}\)：正边（\(B \in X\)） - 边 \(\{A, C\}\)：正边（\(C \in X\)） - 边 \(\{B, C\}\)：假设为负边

三角形中正边数 = 2，这违反了结构平衡属性（不允许2条正边）。

因此 \(\sigma(\{B, C\}) = +\)，即所有节点互为朋友。情况一成立。

第三步：情况二 - \(Y \neq \emptyset\) 时

需要证明三个性质：

(性质i) \(X\) 中任意两节点均为朋友

取任意 \(B, C \in X\)，\(B, C \neq A\)。

已知：\(\sigma(\{A, B\}) = +\) 且 \(\sigma(\{A, C\}) = +\)（因为 \(B, C \in X\)）

反证法：假设 \(\sigma(\{B, C\}) = -\)

考虑三角形 \(\{A, B, C\}\)： - 边 \(\{A, B\}\)：+ - 边 \(\{A, C\}\)：+ - 边 \(\{B, C\}\)：-（假设）

正边数 = 2，违反平衡属性。

因此必有 \(\sigma(\{B, C\}) = +\)。性质i成立。

(性质ii) \(Y\) 中任意两节点均为朋友

取任意 \(D, E \in Y\)，\(D, E \neq A\)。

已知：\(\sigma(\{A, D\}) = -\) 且 \(\sigma(\{A, E\}) = -\)（因为 \(D, E \in Y\)）

反证法：假设 \(\sigma(\{D, E\}) = -\)

考虑三角形 \(\{A, D, E\}\)： - 边 \(\{A, D\}\)：- - 边 \(\{A, E\}\)：- - 边 \(\{D, E\}\)：-（假设）

正边数 = 0，违反平衡属性。

因此必有 \(\sigma(\{D, E\}) = +\)。性质ii成立。

(性质iii) \(X\) 中任意节点与 \(Y\) 中任意节点均为敌人

取任意 \(B \in X\)，\(D \in Y\)。

已知：\(\sigma(\{A, B\}) = +\)，\(\sigma(\{A, D\}) = -\)

反证法：假设 \(\sigma(\{B, D\}) = +\)

考虑三角形 \(\{A, B, D\}\)： - 边 \(\{A, B\}\)：+ - 边 \(\{A, D\}\)：- - 边 \(\{B, D\}\)：+（假设）

正边数 = 2，违反平衡属性。

因此必有 \(\sigma(\{B, D\}) = -\)。性质iii成立。

定理证明完毕。 Q.E.D.

2.4 定理的现实解读

Harary 定理揭示了一个深刻的现象：

任何遵循"两友成敌，两敌成友"局部规则的大型网络，最终必然演化为单极结构或两极结构。这解释了为什么： - 大型社交网络中存在明显的派系划分 - 国际关系中容易形成对立的阵营 - 在线社区中倾向于出现党派分化

三、结构平衡的现实应用（Section 5.3: Applications of Structural Balance）

3.1 国际关系与战争预测

欧洲国家联盟演变（1872-1907）

历史数据分析显示，欧洲列强之间的联盟关系逐步演化为两个对立阵营的过程，完全符合结构平衡理论：

时间序列分析：

  1. 1872年：三皇同盟时期
    • 德国、俄罗斯、奥地利结成同盟
    • 网络结构：接近全正边或单阵营
  2. 1879年：双同盟形成
    • 德国与奥地利结盟（+）
    • 俄罗斯与法国靠近
    • 开始出现二部结构的萌芽
  3. 1894年：俄法同盟
    • 俄罗斯与法国正式结成同盟（+）
    • 形成明显的两极对立
  4. 1904年：英法协约（Entente Cordiale）
    • 英国与法国签订协约
    • 强化二部结构
  5. 1907年：三国协约完成
    • 英国、法国、俄罗斯形成正式同盟
    • 对立的两个阵营：
      • 阵营X：英国、法国、俄罗斯
      • 阵营Y：德国、奥地利
    • 网络接近完全平衡的二部结构

结构平衡理论预测：

Moore（1966）指出，当网络逐步演化到完全平衡的二部结构时，系统的不稳定性达到最高。虽然网络本身是"平衡"的（满足三角形条件），但这种极端的二部划分意味着： - 任何小的冲突可能引发整个阵营间的对抗 - 中立立场变得不可能（任何不选边的行为都会破坏平衡） - 冲突的升级几率大幅增加

历史验证：第一次世界大战（1914-1918）的爆发正是在这种极端平衡的二部结构下发生的。

3.2 Epinions.com：在线信任网络分析

数据背景

Epinions.com 是一个产品评论网站，用户可以： - 标记其他用户为"信任的（Friend）"或"不信任的（Foe）" - 对产品进行评分和评论 - 查看信任用户的评分建议

与标准平衡理论的关键差异：有向边

不同于国家关系的无向图模型，信任关系是有向的（Directed）： - \(A \to B\) 表示 \(A\) 信任 \(B\) - \(B \to A\) 是独立的关系，可能不同

这导致： - 单向信任成为可能 - 信任的传递性不同于无向的互惠关系 - 三角形的定义更加复杂

信任传递性的三种模式：

  1. 正向链（Positive Chain）：\(A \to^+ B \to^+ C\)
    • 预期：\(A\) 应该信任 \(C\)（传递性）
    • 现实符合度：高
  2. 混合链（Mixed Chain）：\(A \to^+ B \to^- C\)
    • 解释：\(A\) 信任 \(B\)，但 \(B\) 不信任 \(C\)
    • 预期：\(A\) 应该不信任 \(C\)（间接不信任）
    • 现实符合度：中等
  3. 负向链（Negative Chain）：\(A \to^- B \to^- C\)
    • 解释：\(A\) 不信任 \(B\)，\(B\) 不信任 \(C\)
    • 预期：\(A\) 是否应该信任 \(C\)？（规则不明确）
    • 实验发现：概率接近50%（不符合"敌人的敌人"规则）

关键发现

相比国际关系的无向模型，Epinions 网络： - 不完全遵循传统平衡理论 - 负向链的传递性远弱于正向链 - 建议算法需要考虑有向信任的特殊性

3.3 动态平衡的演化

现实网络不是静态的，而是不断调整以趋向平衡：

调整机制（Reconciliation Mechanisms）

当出现不平衡三角形时，系统倾向于通过以下方式调整：

  1. 关系翻转：改变某条边的符号（+↔︎-）
  2. 关系强度变化：虽然在二值模型中不体现，但在实际网络中，可能通过削弱关系强度来降低冲突感
  3. 聚类分离：三个节点中的某个节点离群，断开不平衡的三角形

演化速度

  • 高度不平衡的网络（多个不平衡三角形）的调整速度快
  • 接近平衡的网络调整速度慢
  • 网络规模越大，全局平衡化所需时间越长

四、弱结构平衡理论（Section 5.4: Weak Structural Balance）

4.1 James Davis 的改进模型

问题提出

Harary 的原始平衡理论有一个限制：它等同对待两个调和机制： 1. "朋友的朋友应该是朋友"（两个正边自动导致第三条也是正） 2. "敌人的敌人应该是朋友"（两个负边自动导致第三条是正）

但心理学研究（James Davis, 1967）表明这两个机制的强度并不相等： - 机制1很强：人们强烈倾向于使朋友成为朋友 - 机制2很弱：人们对"敌人的敌人"关系不确定

改进方案

Davis 提议修改平衡属性，移除最不稳定的配置（三个敌人都互相对立）：

4.2 弱结构平衡属性的定义

弱结构平衡属性（Weak Structural Balance Property）

对于标记完全图，若不存在任何三节点子图恰好有两条正边和一条负边，则称其满足弱结构平衡属性。

数学表述：图 \(G\) 弱平衡当且仅当：

\[\neg \exists \{u, v, w\} \subset V: |\{e \in E(\{u,v,w\}): \sigma(e) = + \}| = 2\]

等价地说，允许的三角形配置为： - 3条正边（全体互为朋友） - 1条正边（一个同盟对抗共同敌人） - 0条正边（三个敌人）—— 这是关键区别

禁止配置

唯一被禁止的是：2条正边+1条负边的配置（两友一敌）

4.3 弱平衡网络的结构特征化

定理：弱平衡网络的多阵营结构

如果一个标记完全图满足弱结构平衡属性，则其节点可以分为若干组（可能超过两组）\(G_1, G_2, \ldots, G_k\)，使得： - 组内：任意两个在同一组的节点间为 + - 组间：任意两个在不同组的节点间为 -

与强平衡的对比：

属性 强平衡 弱平衡
允许阵营数 最多2个 任意多个
禁止三角形 2正1负、3负 仅2正1负
心理意义 严格的"朋友和敌人" 允许相互敌对但无共同敌人
现实应用 国际政治 学术派系、运动队阵营

4.4 弱平衡定理的证明概要

递归证明框架：

  1. 基础步：选择节点 \(A\) 及其所有朋友组成第一个阵营 \(G_1\)

  2. 递归步：对于 \(A\) 的所有敌人（不在 \(G_1\) 中的节点）组成的子图，递归应用同样的分组逻辑

  3. 终止条件：直到所有节点都被分配到某个阵营

关键论证：

递归分组过程中，每个新发现的阵营内部必然都是正边（通过与 \(A\) 相反的关系和递归性质推导），而不同阵营间必然是负边。

五、高级主题：推广结构平衡理论（Section 5.5: Advanced Material - Generalizing Structural Balance）

5.1 非完全图中的平衡

问题背景

前面的分析都基于完全图假设：任意两个节点间必有边。但真实网络中： - 许多潜在关系未被建立（missing edges） - 不是所有人都直接相识 - 缺失的边可能隐含某种关系态度

5.1.1 两种等价的平衡定义

定义1：补全方法（Completion Approach）

一个不完全的标记图是平衡的，当且仅当可以为所有缺失的边赋予标记，使得得到的完全图满足平衡属性。

\[G \text{ 平衡} \Leftrightarrow \exists \text{补全 } \sigma: E_{\text{missing}} \to \{+, -\}, \text{ 使 } \overline{G} \text{ 满足平衡属性}\]

定义2：二部划分方法（Bipartition Approach）

一个标记图是平衡的，当且仅当其节点可以分为两组 \(X\) 和 \(Y\)，使得： - 所有 \(X\) 内的边（如存在）标记为 + - 所有 \(Y\) 内的边（如存在）标记为 + - 所有跨组的边（如存在）标记为 -

定理：这两个定义是等价的

证明要点： - 若满足定义2，则可以安全地将缺失的同组边补为 +、跨组边补为 -，得到平衡的完全图 - 反之，如果补全后的完全图平衡，则根据 Harary 定理，节点已经被分成两个阵营，这就给出了定义2的分组

5.1.2 圈论特征化（Cycle Characterization）

关键定理：平衡充要条件

一个标记图平衡当且仅当它不包含负边数为奇数的圈。

\[G \text{ 平衡} \Leftrightarrow \text{所有圈中负边数均为偶数}\]

数学直觉：

设想沿着圈走一圈回到起点： - 每条正边 +："保持在同一组" - 每条负边 -：" 切换组"

若负边数为奇数，会奇数次地切换组，最终无法回到起始节点所属的组 → 矛盾。

反之，偶数次切换能保证回到原组，圈上的节点可以一致地分配到两个组中。

算法含义：

可以用 BFS 算法高效检验图的平衡性： 1. 选择任意未访问节点，标记为组0，加入队列 2. 对于每个节点： - 通过正边到达的邻居→分配到同一组 - 通过负边到达的邻居→分配到另一组 3. 若发现同组边（同一组间的正边或不同组间的负边）→ 包含奇圈 → 不平衡 4. BFS 完成且无矛盾 → 平衡

时间复杂度： \(O(n + m)\)（线性复杂度）

5.1.3 "超节点"算法

另一种检验平衡的方法：

  1. 第一步：使用仅含正边的连通性，识别连通分量
    • 每个连通分量→缩为一个"超节点"（Supernode）
    • 形成"超图"（Reduced Graph）
  2. 第二步：在超图层面检查平衡性
    • 将负边都看作超节点间的边
    • 检查这个"负边图"是否为二部图
    • 用二部图判定算法（BFS或DFS）进行检验
  3. 判定逻辑
    • 超图的负边图是二部 → 原图平衡
    • 超图的负边图含奇圈 → 原图不平衡

优点： - 清晰展示平衡的本质：正边形成的聚类，负边形成的二部结构 - 可视化更直观

5.2 近似平衡网络（Approximately Balanced Networks）

5.2.1 不完全平衡的现实情况

在大多数真实网络中，不是所有三角形都平衡，但大多数是平衡的。这引出问题：

如果大约 \((1-\varepsilon)\) 比例的三角形平衡，网络的全局结构会如何？

5.2.2 近似平衡定理

定理：Leskovec-Huttenlocher-Kleinberg, 2010

设 \(G\) 是 \(n\) 节点的完全标记图，若至少 \((1-\varepsilon)\) 的三角形平衡（\(\varepsilon < 1/8\)），则下列之一成立：

(选项a) 存在一个"好"群体： - 存在节点的子集 \(S\)，\(|S| \geq (1-\delta)n\)，其中 \(\delta = O(\sqrt{\varepsilon})\) - 在 \(S\) 内，至少 \((1-\delta)\) 比例的节点对之间为正边 - 即：存在一个大的相对同质的群体

(选项b) 存在一个二部近似： - 节点可分为两个组 \(X\) 和 \(Y\) - 至少 \((1-\delta)\) 比例的边符合二部结构（同组+，异组-） - 即：网络大体上呈现两个对立阵营的结构

参数关系：

\[\delta = O(\sqrt{\varepsilon})\]

例如： - 若 \(\varepsilon = 0.001\)（99.9% 三角形平衡）→ \(\delta \approx 0.032\)（3.2%） - 若 \(\varepsilon = 0.01\)（99% 三角形平衡）→ \(\delta \approx 0.10\)（10%）

这说明即使有小比例的不平衡，网络仍呈现出强的二部或单阵营结构。

5.2.3 定理的证明框架

第一阶段：计数不平衡三角形

完全图 \(K_n\) 中的三角形总数： \[T = \binom{n}{3} = \frac{n(n-1)(n-2)}{6}\]

不平衡三角形数： \[T_{\text{unbal}} \leq \varepsilon T = \frac{\varepsilon n(n-1)(n-2)}{6}\]

第二阶段：节点贡献分析

每个不平衡三角形涉及3个节点。统计有多少个不平衡三角形以某节点 \(v\) 为顶点： \[\sum_{v \in V} u_v = 3 T_{\text{unbal}} \leq \frac{\varepsilon n(n-1)(n-2)}{2}\]

其中 \(u_v\) = 包含节点 \(v\) 的不平衡三角形数。

第三阶段：平均节点贡献

平均而言，每个节点包含于 \(\approx \frac{\varepsilon n^2}{2}\) 个不平衡三角形。

根据鸽笼原理，存在"好"节点 \(A\) 使得 \(u_A \leq \frac{\varepsilon n^2}{2}\)。

第四阶段：分组与错误边计数

以节点 \(A\) 为参考，分组： - \(X\) = {\(A\) 及其所有正边邻居} - \(Y\) = {\(A\) 的所有负边邻居}

分析每个边的"错误"程度： - 若边 \(\{B, C\}\)（\(B, C \in X, B \neq C\)）为负 → 三角形 \(\{A, B, C\}\) 不平衡 - 若边 \(\{D, E\}\)（\(D, E \in Y, D \neq E\)）为负 → 三角形 \(\{A, D, E\}\) 不平衡
- 若边 \(\{B, D\}\)（\(B \in X, D \in Y\)）为正 → 三角形 \(\{A, B, D\}\) 不平衡

第五阶段：界限推导

设错误边数（不符合二部结构的边）为 \(m_{\text{wrong}}\)。则： \[\sum_{v} u_v \geq m_{\text{wrong}}\]（下界）

结合上面的计数，得： \[m_{\text{wrong}} \leq \frac{\varepsilon n^2}{2}\]

正确的边所占比例： \[\frac{m_{\text{correct}}}{m_{\text{total}}} \geq 1 - \frac{\varepsilon n^2/2}{n(n-1)/2} \approx 1 - \varepsilon\]

更精细的分析（使用集中不等式）可得 \(\delta = O(\sqrt{\varepsilon})\) 的界。

5.2.4 应用意义

实际网络分析：

  1. 容错性：即使网络中有小比例的"异常"关系，大体结构仍保持稳定
  2. 预测力：观察部分三角形的平衡性即可推断全网络的结构趋势
  3. 演化预测：如果网络不平衡度在增加，可能预示要出现新的大规模重组

案例

社交网络中的派系分析： - 若观察到 95% 的三角形平衡 - 可以确信网络存在明确的两个主要群体 - 或者存在一个特别大的同质群体 - 异议者/中立者不超过 10% 左右

六、关键概念总结表

英文术语 中文翻译 定义/说明
Network 网络 由节点和边组成的图结构
Positive Edge 正边 标记为 + 的边，表示友谊、联盟、信任
Negative Edge 负边 标记为 - 的边，表示敌对、对抗、不信任
Complete Graph / Clique 完全图；团 任意两节点间都有边的图
Triangle 三角形 三个节点及其三条边组成的子图
Balanced 平衡的 三角形正边数为 1 或 3
Unbalanced 不平衡的 三角形正边数为 0 或 2
Structural Balance Property 结构平衡属性 所有三角形都满足平衡条件
Balance Pressure 平衡压力 不平衡配置产生的心理压力，促使关系调整
Balance Psychology 平衡心理学 研究人们如何通过调整关系来达成心理平衡的学科
Harary's Balance Theorem Harary 平衡定理 刻画平衡图结构的基本定理：单阵营或二部结构
Bipartite Division / Partition 二部划分 将节点分为两个敌对的阵营
Reconciliation 调和 通过改变关系来消除不平衡
Entente Cordiale 协约 特指 1904 年英法协约
Weak Structural Balance 弱结构平衡 禁止"两友一敌"但允许"三敌"的平衡概念
James Davis Model James Davis 模型 改进的弱平衡理论，体现"朋友的朋友"强于"敌人的敌人"
Multi-group Structure 多阵营结构 弱平衡允许的任意多个相互敌对的群体
Directed Edge 有向边 只指向一个方向的边，A→B ≠ B→A
Trust Network 信任网络 以信任/不信任关系为边的网络
Epinions.com Epinions 网站 产品评论和用户信任评级的社交网站
Non-complete Graph 非完全图 某些节点对间没有边的图
Missing Edge 缺失边 不存在但可能被补全的边
Completion Approach 补全方法 通过为缺失边赋值来判断平衡性
Bipartition Approach 二部划分方法 通过寻找二部划分来判断平衡性
Cycle 圈 闭合的节点路径
Cycle Characterization 圈论特征化 用圈中负边的奇偶性判断平衡性
Odd Cycle 奇圈 包含奇数条边的圈
Even Cycle 偶圈 包含偶数条边的圈
Supernode 超节点 通过正边的连通分量缩为一个单元
Reduced Graph 缩图 以超节点为顶点、负边为边的图
BFS / Breadth-First Search 广度优先搜索 逐层遍历的图搜索算法，用于二部性检验
Approximately Balanced 近似平衡 大多数（但非全部）三角形平衡的网络
Leskovec-Huttenlocher-Kleinberg Theorem LHK 定理 关于近似平衡网络结构的定理
Good Community 好群体 近似平衡定理中的大型同质群体
Bipartite Approximation 二部近似 近似平衡定理给出的二部结构
Enemy of My Enemy 敌人的敌人 负-负链的直观表述
Friend of My Friend 朋友的朋友 正-正链的直观表述
International Relations 国际关系 应用平衡理论的重要领域
Alliance 联盟 国家间的正式或非正式合作关系
Antagonism 对抗；敌对 国家间的冲突或不信任关系
Bloc / Alignment 阵营；集团 有共同利益的国家组合
World War I / WWI 第一次世界大战 平衡理论用于解释的历史事件
Moore (1966) Moore (1966) 应用平衡理论分析巴基斯坦分裂和美中关系的研究
Directed Graph 有向图 边有方向的图
Transitivity 传递性 关系沿着路径传播的性质
Heuristic 启发式规则 基于心理直觉的决策规则
Stability 稳定性 系统抵抗变化的能力
Error / Wrong Edge 错误边 不符合预期结构的边
Fraction 比例；分数 总体中的相对数量
Concentration Inequality 集中不等式 表明随机变量接近其期望值的概率不等式

七、深度学习指引

7.1 核心理解层次

初级理解：配置识别 - 能够快速判断任意三角形的四种配置 - 理解为什么"两友一敌"和"三敌"会产生压力 - 掌握 1 或 3 个正边的判断规则

中级理解：定理与证明 - 理解 Harary 定理为何如此强大（局部→全局） - 能够跟随证明中的逻辑推导 - 认识到平衡约束的强制力量

高级理解：推广与应用 - 理解非完全图中平衡的多种等价刻画 - 掌握近似平衡的含义和实际意义 - 能够分析复杂网络中的部分不平衡现象

7.2 与其他章节的联系

  • 第3章（强弱关系）：关系强度与平衡的交互作用
  • 第4章（社区结构）：社区与平衡阵营的关系
  • 第8章（动力学过程）：平衡如何在网络演化中实现
  • 第12章（信息传播）：不同符号边上的信息扩散差异

7.3 课程项目建议

  1. 历史数据分析项目
    • 收集 1870-1920 年欧洲国家关系数据
    • 构造边标记图，检验平衡性演变
    • 可视化关键时间点的网络结构
  2. 在线社区派系识别
    • 从 Twitter/Reddit 获取用户互动和意见标签
    • 分析三角形平衡性与意见一致性的关系
    • 尝试用二部模型预测派系划分
  3. 推荐系统中的信任建模
    • 在信任网络中应用弱平衡理论
    • 设计新的信任推导机制
    • 与传统协作过滤比较性能

文档版本：1.0
最后更新：2026-04-11
维护者：COMP5313 教学团队