COMP5313 考试 Cheatsheet（六大模块速查）

Posted on Edited on In , Word count in article: 4.4k Reading time ≈ 16 mins.

COMP5313 考试 Cheatsheet — 六大模块速查

覆盖 Week 1-6，按六大知识模块组织，供考场快速回顾。 教材：Networks, Crowds, and Markets (Easley & Kleinberg) + Mining of Massive Datasets Ch5 + Barabási Network Science

一、图与网络基础（Graph Basics）

1.1 基础定义

  • 图（Graph）：\(G = (V, E)\)，节点集 \(V\)、边集 \(E\)
  • 邻居（Neighbors）：若 \((u,v) \in E\)，则 \(u, v\) 互为邻居
  • 度（Degree）：节点连接的边数；有向图分出度 \(d^{out}\)、入度 \(d^{in}\)
  • 无向图：边对称；有向图：边有方向（Web、Twitter 关注）
  • 应用：社交（Facebook）、通信（Arpanet）、信息（Web）、生物（PPI）

1.2 路径与环

  • 路径（Path）：节点序列，相邻节点间有边
  • 简单路径（Simple Path）：不重复节点
  • 环（Cycle）：首尾相同的路径，长度 ≥ 3
  • 路径长度：边数
  • 距离 \(d(u,v)\)：最短路径长度
  • 直径（Diameter）：\(\max_{u,v} d(u,v)\)

1.3 连通性

  • 连通（Connected）：无向图中任意两节点有路径
  • 连通分量（Connected Component, CC）：极大连通子图
  • 巨分量（Giant Component）：占节点相当比例的大分量；通常只有一个——两个巨分量只需 1 条边即合并
  • 有向图：
    • 强连通（Strongly Connected）：任意两点互有有向路径
    • 强连通分量（SCC）：极大强连通子图

1.4 图搜索

  • BFS（广度优先搜索）：从起点逐层展开；自然产生 BFS 层次结构
  • BFS 层次：层 \(d\) 的所有节点到起点距离为 \(d\)
  • 边只连接同层或相邻层节点（无向图中）
  • 可在 \(O(|V|+|E|)\) 时间内求单源最短路径

1.5 网络现象

  • 小世界现象（Small World）：大规模网络中任意两点平均距离很短（log 级别）

二、社交网络局部结构（Local Structure）

2.1 三元闭包（Triadic Closure）

  • 定义：若 \(A\)-\(B\) 和 \(A\)-\(C\) 是朋友 → \(B\)-\(C\) 成为朋友的概率高
  • 驱动：机会、信任、激励
  • 聚类系数（Clustering Coefficient）： \[C(v) = \frac{\text{v 的朋友间实际边数}}{\binom{d_v}{2}}\]
  • 取值 \([0,1]\)；全网平均 = Average Clustering Coefficient

2.2 强联系 vs 弱联系

  • 强联系（Strong Tie）：频繁互动、情感投入高（亲友）
  • 弱联系（Weak Tie）：偶然接触（熟人）

2.3 桥与跨度

  • 桥（Bridge）：删除后端点不连通的边（现实网络中极少）
  • 局部桥（Local Bridge）：两端点无共同邻居 的边，等价：删除后两端距离 > 2
  • 跨度（Span）：删除 local bridge 后两端点的距离

2.4 强三元闭包性质（Strong Triadic Closure, STC）

  • 定义：节点 \(A\) 若有 ≥ 2 个强联系 \(B, C\)，则 \(B\)-\(C\) 必须有边（强或弱）
  • 关键定理：若 \(A\) 满足 STC 且至少有 2 个强联系，则 \(A\) 的所有局部桥必为弱联系
  • 反证法证明：假设 \(A\)-\(B\) 是强的局部桥，\(A\)-\(C\) 也为强 → 由 STC 必有 \(B\)-\(C\) → 违反局部桥定义（公共邻居 \(A\)）

2.5 邻域结构

  • 邻域重叠（Neighborhood Overlap）： \[O(A,B) = \frac{|N(A) \cap N(B)|}{|N(A) \cup N(B) \setminus \{A,B\}|}\]
  • 局部桥的 overlap = 0
  • 嵌入度（Embeddedness）：一条边两端点的公共邻居数
  • 结构洞（Structural Hole）：节点位于多个不互动群体的交界 → 控制信息流（Burt）

三、社区发现与图划分（Community Detection）

3.1 图划分基础

  • 目标：将网络分为紧密区域，区域间连接稀疏
  • 分裂式（Divisive）：移除"跨区"边；自顶向下
  • 聚合式（Agglomerative）：合并相似节点；自底向上
  • 树状图（Dendrogram）：合并/分裂过程；水平切割得分区

3.2 社区定义

  • 直觉：内密集、外稀疏的节点集
  • 团（Clique）：完全子图（过严格）
  • 强社群：每个节点 \(k_i^{int} > k_i^{ext}\)
  • 弱社群：\(\sum k_i^{int} > \sum k_i^{ext}\)

3.3 中介性（Betweenness）

  • 边中介性： \[b(e) = \sum_{s \neq t} \frac{\sigma_{st}(e)}{\sigma_{st}}\] 其中 \(\sigma_{st}\) 为 \(s\)-\(t\) 最短路径数，\(\sigma_{st}(e)\) 为经过 \(e\) 的
  • 节点中介性：类似定义
  • 流量直觉：每对节点 1 单位流量平分给所有最短路径

3.4 Girvan-Newman 算法

  1. 计算所有边的 betweenness
  2. 移除最高 betweenness 的边
  3. 重新计算（重要！）所有 betweenness
  4. 若产生新分量 → 记录；继续直至所有边移除
  • 时间复杂度：\(O(nm)\) 算一次 betweenness；完整 \(O(nm^2)\)，稀疏图 \(O(n^3)\)

3.5 Betweenness 的 BFS 计算（3 步）

步骤 1：BFS 分层（从起点 \(A\)）

步骤 2：最短路径数自顶向下 - 第 1 层节点：\(\sigma_A(X) = 1\) - 第 \(d\) 层节点 \(X\)：\(\sigma_A(X) = \sum_{Y \in \text{上方邻居}} \sigma_A(Y)\)

步骤 3：流量自底向上 - 叶节点：1 单位流量（自身） - 中间节点 \(X\)：流量 = \(1 + \sum_{\text{下方流入}}\) - 按 \(\sigma_A(Y) / \sigma_A(X)\) 比例分配给上方邻居 \(Y\)

对每个起点重复，流量求和，最后除以 2（每对被计算两次）

3.6 Modularity（模块度）

\[Q = \sum_{s \in S} \left[\frac{m_s}{m} - \left(\frac{D_s}{2m}\right)^2\right]\] - \(m_s\)：社区 \(s\) 内部边数；\(D_s\)：社区内度数总和；\(m\)：总边数 - 取值 \([-1, 1]\)；\(Q > 0\) 意味有社区结构 - 假设 H3：随机网络无社群结构 - 假设 H4：最大 \(Q\) 对应最优分区 - Louvain：贪心最大化 \(Q\)，\(O(N \log^2 N)\) - 局限： - 分辨率极限：无法识别 \(< \sqrt{2L}\) 的小社群 - 模块度高原：最大值不唯一

四、网络形成与同质性（Homophily & Formation）

4.1 同质性（Homophily）

  • 定义：人们倾向与相似的人建立关系
  • 检测（2pq 测试）：在二分类（比例 \(p\) 男、\(q\) 女）网络中，随机图中跨组边比例期望为 \(2pq\)
    • 实际 < \(2pq\) → 存在 homophily
  • 两大驱动：
    • 选择（Selection）：相似 → 变朋友
    • 社会影响（Social Influence）：朋友 → 变相似

4.2 从属网络（Affiliation Network）

  • 二部图（Bipartite Graph）：两类节点（人 ↔︎ 活动），边跨类
  • 融合网络：社交网络 + 二部图
  • Focal Point：共同活动/焦点

4.3 三种闭包机制

机制 描述 类型
三元闭包（Triadic Closure） 共同朋友 → 成为朋友 选择
焦点闭包（Focal Closure） 共同活动 → 成为朋友 选择
成员闭包（Membership Closure） 朋友参加的活动 → 自己加入 社会影响

实证（email 数据）：共同朋友数 ↑ → 未来成为朋友的概率近线性上升

4.4 Schelling 隔离模型

  • 网格上两类 agent（如红/蓝）
  • 阈值 \(T\)：同类邻居 ≥ \(T\) 才满意
  • 不满意 → 迁移到随机空位
  • 惊人发现：即使 \(T=3\)（邻居中 3/8 同类即满意），也会产生大片同质区
  • 结论：微弱偏好 → 宏观隔离

五、正负关系与结构平衡（Signed Networks）

5.1 正负边模型

  • 符号图（Signed Graph）：每条边标 \(+\)（朋友/信任/同盟）或 \(-\)（敌人/不信任/对立）— 捕捉人际/政治关系的两极性
  • 应用：国际关系（冷战两阵营）、信任网络（Epinions、Slashdot）、社交对立（Wikipedia 编辑纠纷）

5.2 三角形四种配置（完全图）

配置 符号 平衡？ 社会解释 心理稳定性
\(+++\) 3 正 ✓ "朋友的朋友是朋友"（\(A,B,C\) 三人互为朋友） 稳定
\(++-\) 2 正 1 负 ✗ \(A\) 同时是 \(B\) 和 \(C\) 的朋友，但 \(B\)-\(C\) 敌对 → \(A\) 压力大 不稳定
\(+--\) 1 正 2 负 ✓ "敌人的敌人是朋友"（\(A\)-\(B\) 友，共同敌对 \(C\)） 稳定
\(---\) 3 负 ✗ "全员敌对" → 任两者有联合对抗第三者的动机 不稳定

平衡规则（形式化）：三角形 \((A,B,C)\) 平衡 \(\Leftrightarrow\) 三边符号乘积 \(= +\) \(\Leftrightarrow\) 含奇数条正边（即 1 或 3 条）；也可记为"负边数为偶数（0 或 2）"

5.3 结构平衡（Structural Balance）

  • 局部定义：完全符号图是结构平衡的（structurally balanced），若每一个三角形都是平衡的——即整图不包含任何 \(++-\) 或 \(---\) 三角形
  • 平衡压力：不平衡的三角形（\(++-\)、\(---\)）产生社会心理张力，驱动关系重新配置（如 \(B\)-\(C\) 从敌变友将 \(++-\) 转为 \(+++\)）
  • 动态视角：在演化中，网络倾向于移除不平衡三角形 → 走向结构平衡状态（虽然现实网络未必完全到达）

5.4 Harary 平衡定理（完全图）【必背】

定理（Cartwright-Harary 1956）：完全有标签图 \(G\) 是结构平衡的 \(\Leftrightarrow\) 节点可以划分为两个集合 \(X, Y\)（其中一个可为空），使得 - 组内（\(X\) 内部 或 \(Y\) 内部）所有边为正 - 组间（\(X\) 与 \(Y\) 之间）所有边为负

等价表述：整图由两个"派系"组成，派系内友好、派系间敌对；允许 \(Y = \emptyset\)（此时所有边为正）。

证明（\(\Leftarrow\) 方向，简单）：任取三角形 \((A,B,C)\)。三节点分到 \(X,Y\) 两组必然出现"全同组（3 正边）"或"2 同 1 异（1 正 2 负）"——两种情形都是奇数正边 → 平衡。

证明（\(\Rightarrow\) 方向，构造性 BFS 法）： 1. 选起点：任取节点 \(A\)，定义 \(X = \{A\} \cup \{B : A\text{-}B \text{ 为正}\}\)（\(A\) 和 \(A\) 的所有朋友），\(Y = \{C : A\text{-}C \text{ 为负}\}\)（\(A\) 的所有敌人） 2. 证 \(X\) 内全正：取 \(B_1, B_2 \in X \setminus \{A\}\)。三角形 \((A, B_1, B_2)\) 中 \(A\text{-}B_1 = +\)、\(A\text{-}B_2 = +\)（由 \(X\) 定义）。由平衡需奇数正边 → \(B_1\text{-}B_2 = +\) ✓ 3. 证 \(Y\) 内全正：取 \(C_1, C_2 \in Y\)。三角形 \((A, C_1, C_2)\) 中 \(A\text{-}C_1 = -\)、\(A\text{-}C_2 = -\)（两条负边）。奇数正边 → \(C_1\text{-}C_2 = +\) ✓（敌人的敌人是朋友） 4. 证 \(X\)-\(Y\) 间全负：取 \(B \in X\)、\(C \in Y\)。若 \(B = A\)，则由 \(Y\) 定义 \(A\text{-}C = -\)；若 \(B \neq A\)，三角形 \((A, B, C)\) 中 \(A\text{-}B = +\)、\(A\text{-}C = -\)（一正一负）。奇数正边 → \(B\text{-}C = -\) ✓ 5. 归纳：对所有节点对成立 → 划分有效 ∎

直观推论： - 完全平衡图的结构极为受限——从 \(A\) 的朋友/敌人二分即完全决定其余所有关系 - 若图中任何一对敌人间关系混合（有正有负） → 必不平衡 - 现实中的近似平衡（approximate balance）：真实大型完全符号图中多数三角形平衡即可

5.5 一般图（非完全）的结构平衡

定义难点：一般图中可能有些节点对无边，不能直接套用"每个三角形平衡"。

两个等价定义： 1. 补边定义：能否为缺失的边赋予 \(+/-\) 标签，使补全后的完全图结构平衡 → 若能则原图平衡 2. 二分定义：节点能否划分为 \(X, Y\)，使组内现有边全为正、组间现有边全为负（缺失边不作要求）

关键定理（环的奇偶性刻画）：一般符号图是结构平衡的 \(\Leftrightarrow\) 图中不存在含奇数条负边的环（即所有环的负边数为偶数）

证明思路： - \(\Rightarrow\)：若分成 \(X,Y\) 两组，任一环从某节点出发回到自身 → 跨组跳转偶数次 → 负边数必为偶数 - \(\Leftarrow\)：所有环负边数为偶数时，可从任一节点 BFS，按路径上负边奇偶性二分节点，保证无冲突

5.6 BFS 检验平衡性（两步算法）【必会】

Step 1（正边分量）：忽略负边，在正边子图上找连通分量（称为 supernodes） - 在每个 supernode 内，任意两节点间存在全正路径 → 它们必须同组 - 若某 supernode 内部含任何一条负边 → 立即判定不平衡（因为这条负边构成含 1 条负边的奇环）

Step 2（缩点+二部图检测）：将每个 supernode 缩为单个超级节点，原始负边成为超图上的边 → 构造"缩点图"，该图只含"负边" - 对缩点图做 BFS：起点标组 0，邻居标组 1，交替分层 - 若某负边两端标到同一组 → 存在奇数环 → 不平衡 - 若无冲突 → 平衡，BFS 二分即为 \(X, Y\)

替代（一步 BFS/DFS）：直接在原图 BFS，维护每个节点的组标签 - 遇 \(+\) 边：两端同组 - 遇 \(-\) 边：两端异组 - 若产生矛盾 → 不平衡；否则平衡

复杂度：\(O(|V| + |E|)\)，与一般 BFS 同阶

6.1 搜索排序问题

  • 信息检索问题：同义（synonymy）、多义（polysemy）
  • Web 规模 → 从 scarcity 到 abundance
  • 需要从大量相关文档中筛选"最重要"的

6.2 HITS（Hubs and Authorities）

  • Authority：高质量内容页
  • Hub：指向多个好 authority 的列表页
  • 相互递归：好 hub 指好 authority；好 authority 被好 hub 指
  • 初始：所有分数 = 1
  • Authority Update：\(\text{auth}(p) = \sum_{q \to p} \text{hub}(q)\)
  • Hub Update：\(\text{hub}(p) = \sum_{p \to q} \text{auth}(q)\)
  • 归一化：除以总和（或最大值）
  • 矩阵形式：
    • \(\mathbf{a} = L^T \mathbf{h}\)；\(\mathbf{h} = L\mathbf{a}\)
    • \(\mathbf{h}^{(K)} \propto (LL^T)^K \mathbf{h}^{(0)}\)
    • 收敛到 \(LL^T\) 最大特征值对应的特征向量
  • 优点：无 dead end/spider trap 问题；查询相关

6.3 PageRank 基础

  • 核心：一个分数；页面均分 PR 给所有出链
  • Basic Update： \[v'_i = \sum_{j \to i} \frac{v_j}{d_j^{out}}\]
  • 死端：将 PR 传给自己（Easley-Kleinberg 约定）
  • 矩阵形式：\(\mathbf{v}' = M \mathbf{v}\)，\(M\) 是列随机矩阵
  • 均衡：\(\mathbf{v} = M\mathbf{v}\) 且 \(\sum v_i = 1\)
  • 主特征向量：\(M\) 的 \(\lambda = 1\) 特征向量

6.4 PageRank 问题

问题 描述 后果
死端（Dead End） 无出链的节点 PR 逐渐泄漏到死端 → 其他节点归零
蜘蛛陷阱（Spider Trap） 有出链但形成封闭子图 PR 全部聚集在陷阱内
不收敛 如 4 节点循环 PR 永远震荡

收敛条件：强连通 + 非周期

6.5 Scaled PageRank（实际使用）

\[v'_i = \alpha \cdot (Mv)_i + \frac{1-\alpha}{n}\] - \(\alpha\)（或 \(\beta\)）：阻尼因子，常用 \(0.8 \sim 0.9\)（Google：0.85） - 直觉：随机冲浪者以 \(\alpha\) 跟随链接，以 \(1-\alpha\) 跳转到随机页面（传送/Teleportation） - 水循环类比：蒸发 \(1-\alpha\) 单位再均匀降雨 - 等价随机游走：稳态分布 = PR 极限值 - 性质： - 消除死端/陷阱问题 - 误差按 \(\alpha^K\) 指数衰减 - 均衡：\(\mathbf{v} = \frac{1-\alpha}{n}(I - \alpha M)^{-1}\mathbf{e}\) - \((I - \alpha M)\) 可逆（严格对角占优）

6.6 Personalized PageRank (PPR) & Topic-Sensitive

\[v' = \alpha M v + (1-\alpha) \frac{\mathbf{e}_S}{|S|}\] - 随机跳转仅跳到 \(S\)（teleport set） - Topic-sensitive：\(S\) = 该主题的网页集（如 DMOZ 16 大类） - TrustRank：\(S\) = 可信页面（.edu/.gov），用于反垃圾 - Spam Mass：\(\frac{r - t}{r}\)，\(r\) = PR，\(t\) = TrustRank；接近 1 → 疑似垃圾

6.7 链接垃圾与 Spam Farm

  • Spam Farm 结构：目标页 \(t\)、\(m\) 支持页；\(t\)↔︎支持页互链
  • 放大效应（\(\beta=0.85\)）：外部 PR 贡献放大 \(\frac{1}{1-\beta^2} \approx 3.6\)
  • 支持页还能占 \(\frac{\beta}{1+\beta} \cdot \frac{m}{n} \approx 0.46 \frac{m}{n}\)

6.8 Web 图蝴蝶结结构（Bow-Tie）

Broder et al. 1999（AltaVista 数据）： | 部分 | 规模 | 描述 | |------|------|------| | SCC | 56M | 巨强连通分量；核心 | | IN | 44M | 可达 SCC，不可被 SCC 达 | | OUT | 44M | 被 SCC 达，不可达 SCC | | Tendrils | 44M | 从 IN 可达但不到 SCC；或能到 OUT 但不从 SCC 达 | | Tubes | 小 | 从 IN 直通 OUT 绕过 SCC | | Disconnected | 小 | 完全孤立 |

6.9 工程优化

  • 稀疏矩阵存储：列式 (source, degree, destinations)；每非零 ~4 字节
  • MapReduce PR：M 按条纹（stripe）或方块（\(k^2\) blocks）分区；v 条纹配合
  • 大规模 PR：50-75 次迭代足够

七、证明题重点

7.1 STC → 局部桥为弱联系（反证法）

设 \(A\) 满足 STC，\(A\)-\(B\) 为强的局部桥： - 由 STC，\(A\) 若有另一强联系 \(A\)-\(C\)，则 \(B\)-\(C\) 必有边 - 但局部桥要求 \(B, C\) 无共同邻居以外的连接 ⇒ 矛盾

7.2 Harary 平衡定理（完全图）

  • \(\Rightarrow\)：若分成 \(X, Y\)，任何三角形至少两顶点同组 → 内正外负推出奇数正边
  • \(\Leftarrow\)：选一负边节点 \(A\)，用 BFS 按"朋友/敌人"划分组别，利用平衡条件推出组内全正、组间全负

7.3 不平衡 \(\Leftrightarrow\) 奇数负边环

  • \(\Rightarrow\)：不平衡的完全图有不平衡三角形，即 1 条或 3 条负边（奇数）
  • \(\Leftarrow\)：若所有环负边数均为偶数，可用 BFS 按路径奇偶性二分节点

7.4 Scaled PR 矩阵可逆

  • \((I - \alpha M)\) 严格对角占优：对角 \(= 1\)，每行非对角和 \(\le \alpha < 1\)
  • 对角占优矩阵可逆（Gershgorin）

八、核心计算技巧速查

8.1 PageRank 计算

基本 PR（3 节点例）：列方程 \(v = Mv + \sum v_i = 1\)，代入消元 Scaled PR（\(\alpha = 4/5\)）：\(v'_i = \alpha (Mv)_i + \frac{1-\alpha}{n}\)

8.2 HITS 两步计算

  1. Round 1：auth = hub 之和；hub = auth 之和
  2. Round 2：同上
  3. 归一化：除以总和

8.3 Edge Betweenness 手算

  1. 对每节点 BFS
  2. 上传/下传数最短路径
  3. 流量按比例分配
  4. 求和除 2

8.4 Clustering Coefficient

\[C(v) = \frac{2 \cdot (\text{v 朋友间边数})}{d_v (d_v - 1)}\]

8.5 Modularity

对每社区：\(\frac{m_s}{m} - \left(\frac{D_s}{2m}\right)^2\)，求和

8.6 Neighborhood Overlap

\[O(A,B) = \frac{|N(A) \cap N(B)|}{|N(A) \cup N(B) \setminus \{A,B\}|}\]

九、概念辨析

对比 A B
Bridge vs Local Bridge 删除后端点不连通 删除后端点距离 > 2
强联系 vs 弱联系 亲密、投入高 熟人、频次低
有向图连通 vs 强连通 忽略方向连通 沿方向互达
Hub vs Authority 指向者 被指向者
Basic vs Scaled PR 有陷阱/死端问题 有 teleport 修正
Selection vs Social Influence 先相似后结识 结识后趋于相似
强社群 vs 弱社群 每节点内度 > 外度 社群总内度 > 总外度
Focal vs Membership Closure 共同活动 → 朋友 朋友 → 共同活动

十、考试 Tips

  1. 证明题：STC / Balance Theorem / 奇数负边环 / Scaled PR 可逆
  2. 计算题：PageRank 均衡值、HITS 迭代、Edge Betweenness、Modularity
  3. 概念辨析：Bridge/Local Bridge、有向连通、HITS vs PageRank
  4. 算法理解：BFS、Girvan-Newman、HITS、Scaled PageRank
  5. 建图分析题：Spam Farm 放大、Bow-Tie 结构判定
  6. 矩阵表示：邻接、行/列随机、\(AA^T\) 特征向量

高频公式必背： - \(O(A,B) = |N(A) \cap N(B)| / |N(A) \cup N(B) \setminus \{A,B\}|\) - \(Q = \sum_s [m_s/m - (D_s/2m)^2]\) - \(v'_i = \alpha(Mv)_i + (1-\alpha)/n\) - auth/hub 更新规则 - 2pq 测试

速算技巧： - 无入链节点：basic PR = 0 - 无出链节点：basic PR 累积；scaled PR 仍被 teleport 修正 - 对称图：对称节点 PR 相等

文档版本：2026-04-16 祝考试顺利！ ✨