COMP5313 Assignment 1 题解 03 - Structural Balance

COMP5313 Assignment 1 题解（三）

Task 3 — Structural Balance

题目

Figure 3(a) 和 Figure 3(b) 给出了两个带正负号的社交网络。题目要求用 lecture 中讲的 two-step approach 判断这两个 signed network 是否 balanced。

这一题按 lecture 里的 two-step approach 来判断：

1. 任选一个点放进阵营 ；
2. 正边两端放同一阵营，负边两端放不同阵营；
3. 如果推导过程中出现矛盾，则图不 balanced；如果能完整分成两个阵营，则 balanced。

---

Figure 3(a)

按图中的符号，从 开始：

• 是负边，所以
• 是负边，所以
• 是负边，所以
• 是正边，所以
• 是负边，所以
• 是负边，也能推出 ，这里还一致
• 是负边，所以
• 但 是正边，所以 和 应该在同一阵营

这里出现矛盾：

• 由 可知，正边 要求
• 但由负边 且 ，又推出

因此 Figure 3(a) 不是 balanced graph。

---

Figure 3(b)

同样从 开始：

• 是负边，所以
• 是负边，所以
• 是负边，所以
• 是正边，所以
• 是正边，所以
• 是正边，所以
• 是正边，所以

但图中 是负边，这就要求：

这与上面推出的

矛盾。

因此 Figure 3(b) 也不是 balanced graph。

---

最终答案

• Figure 3(a): not balanced
• Figure 3(b): not balanced

即：