COMP5313 Assignment 1 题解（三）
COMP5313 Assignment 1 题解（三）
Task 3 — Structural Balance
题目
Figure 3(a) 和 Figure 3(b) 给出了两个带正负号的社交网络。题目要求用 lecture 中讲的 two-step approach 判断这两个 signed network 是否 balanced。
先理解 balanced 到底是什么意思
这里边上的符号表示：
- \(+\)：正关系
- \(-\)：负关系
lecture 里的核心结论是：
一个 signed graph 是 balanced，当且仅当它的节点可以分成两个阵营，使得：
- 阵营内部全是正边；
- 阵营之间全是负边。
所以做题时，本质上就是检查：
这张图能不能被一致地分成两组？
如果可以，就是 balanced；如果中途推出矛盾，就是 not balanced。
two-step approach 做题时怎么落地
lecture 里的正式版本会先看 positive edges、再压成 supernodes；但手算时更直观的等价写法是：
- 任选一个点放进阵营 \(X\)；
- 遇到正边，就把另一端放进同一阵营；
- 遇到负边，就把另一端放进另一阵营；
- 一直沿着图往外推；
- 如果某个节点被同时要求属于两个不同阵营，就说明图不 balanced。
你可以把它记成三句话：
- 正边：同组
- 负边：异组
- 推出矛盾：not balanced
Figure 3(a)
先把图上的关键边看清楚。Figure 3(a) 里我们会用到这些边：
- \(IA\) 是负边
- \(IG\) 是负边
- \(GH\) 是负边
- \(HF\) 是负边
- \(FG\) 是正边
- \(HE\) 是正边
- \(FE\) 是负边
- \(AB\) 是负边
- \(BE\) 是负边
- \(BC\) 是负边
- \(BD\) 是负边
- \(CD\) 是正边
现在开始分组。设
\[ A \in X \]
第一步：由 \(A\) 往外推
因为 \(IA\) 是负边，所以
\[ I \in Y \]
因为 \(AB\) 是负边，所以
\[ B \in Y \]
第二步：继续由 \(I\) 和 \(B\) 往外推
因为 \(IG\) 是负边，而 \(I \in Y\)，所以
\[ G \in X \]
因为 \(BE\) 是负边，而 \(B \in Y\)，所以
\[ E \in X \]
因为 \(BC\) 是负边，而 \(B \in Y\)，所以
\[ C \in X \]
因为 \(BD\) 是负边，而 \(B \in Y\)，所以
\[ D \in X \]
第三步：检查其他边是否一致
因为 \(CD\) 是正边，正边要求同组；而我们已经推出
\[ C \in X, \quad D \in X \]
这一步是一致的，没有问题。
因为 \(GH\) 是负边，而 \(G \in X\)，所以
\[ H \in Y \]
因为 \(HE\) 是正边，正边要求同组；而 \(E \in X\)，所以这条边要求
\[ H \in X \]
这就和上一步矛盾了：
\[ H \in Y \quad \text{and} \quad H \in X \]
也就是说：
- 由负边 \(GH\) 推出 \(H\) 必须和 \(G\) 异组；
- 由正边 \(HE\) 又推出 \(H\) 必须和 \(E\) 同组；
- 但前面已经有 \(G \in X\) 且 \(E \in X\)，所以这两个要求互相冲突。
因此 Figure 3(a) 不能被一致地分成两个阵营，所以：
\[ \boxed{\text{Figure 3(a) is not balanced.}} \]
Figure 3(b)
Figure 3(b) 的关键边是：
- \(IA\) 是负边
- \(IG\) 是负边
- \(GH\) 是正边
- \(HF\) 是正边
- \(FG\) 是正边
- \(FE\) 是负边
- \(AB\) 是正边
- \(BE\) 是正边
- \(BC\) 是正边
- \(BD\) 是正边
- \(CD\) 是负边
同样从
\[ A \in X \]
开始。
第一步：由 \(A\) 往外推
因为 \(IA\) 是负边，所以
\[ I \in Y \]
因为 \(AB\) 是正边，所以
\[ B \in X \]
第二步：继续往外推
因为 \(IG\) 是负边，而 \(I \in Y\)，所以
\[ G \in X \]
因为 \(GH\) 是正边，而 \(G \in X\)，所以
\[ H \in X \]
因为 \(HF\) 是正边，而 \(H \in X\)，所以
\[ F \in X \]
因为 \(FE\) 是负边，而 \(F \in X\)，所以
\[ E \in Y \]
另一方面，因为 \(BE\) 是正边，而 \(B \in X\)，所以又必须有
\[ E \in X \]
这就产生了直接矛盾：
\[ E \in Y \quad \text{and} \quad E \in X \]
也就是说：
- 左边这部分通过 \(G\)-\(H\)-\(F\)-\(E\) 推下来，要求 \(E\) 与 \(F\) 异组，所以 \(E \in Y\)；
- 右边通过正边 \(AB\) 和 \(BE\) 推下来，又要求 \(E\) 与 \(B\) 同组，所以 \(E \in X\)。
两个要求不能同时成立，因此 Figure 3(b) 也不能被一致地分成两个阵营。
所以：
\[ \boxed{\text{Figure 3(b) is not balanced.}} \]
最终答案
- Figure 3(a): not balanced
- Figure 3(b): not balanced
即：
\[ \boxed{\text{Both Figure 3(a) and Figure 3(b) are not balanced.}} \]