COMP5313 Tutorial 06 - PageRank 题解
Week 6 Tutorial: PageRank 题解
课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 主题：PageRank 的定义与计算 依据教材 Networks, Crowds, and Markets（Easley & Kleinberg）第 14.3 节
一、预备知识回顾
1.1 基本 PageRank 更新规则（Basic PageRank Update Rule）
网络有 \(n\) 个节点，所有节点初始 PageRank 值为 \(1/n\)。
更新规则： > 每个页面将其当前 PageRank 均等地（equally）分给每条出链（out-going link），送给其指向的页面。若某页面没有出链，则把自己的 PageRank 全部传给自己（即保留不变）。
数学形式： \[v'_i = \sum_{j \to i} \frac{v_j}{d_j^{out}}\] 其中 \(d_j^{out}\) 为节点 \(j\) 的出度；若 \(d_j^{out}=0\) 则 \(v'_j = v_j\)（保留自身）。
矩阵形式：\(v' = M v\)，其中 \(M\) 是列随机的转移矩阵（column-stochastic transition matrix）。
1.2 均衡 PageRank 值（Equilibrium PageRank）
均衡条件： \[v = Mv\]
即再次应用更新规则时所有分数不变。同时有 \(\sum_i v_i = 1\)（归一化条件）。
1.3 缩放 PageRank（Scaled PageRank）
为避免 Spider Trap（自环陷阱）和 Dead End（死端）问题，引入缩放因子 \(\alpha \in (0, 1)\)（常用 \(0.8 \sim 0.9\)）。
缩放更新规则： \[v' = \alpha M v + \frac{1-\alpha}{n} \mathbf{e}\]
其中 \(\mathbf{e}\) 是全 1 向量。直观解释：以概率 \(\alpha\) 跟随链接浏览，以概率 \(1-\alpha\) 随机跳转到任意节点。
二、练习 1：基本 PageRank 值计算
2.1 Figure 1(a)：三节点图
图结构：节点 \(\{a, b, c\}\)，边集： - \(a \to b\)，\(b \to a\)（双向） - \(a \to c\) - \(c \to b\) - \(c \to c\)（自环）
出度： | 节点 | 出度 | 出链目标 | |------|------|----------| | \(a\) | 2 | \(b, c\) | | \(b\) | 1 | \(a\) | | \(c\) | 2 | \(b, c\) |
建立均衡方程 \(v = Mv\)：
\[v_a = \frac{v_b}{1} = v_b\]
\[v_b = \frac{v_a}{2} + \frac{v_c}{2}\]
\[v_c = \frac{v_a}{2} + \frac{v_c}{2}\]
归一化条件：\(v_a + v_b + v_c = 1\)。
求解：
从第三式：\(v_c - \frac{v_c}{2} = \frac{v_a}{2}\)，即 \(\frac{v_c}{2} = \frac{v_a}{2}\)，故 \(v_c = v_a\)。
代入第二式：\(v_b = \frac{v_a}{2} + \frac{v_a}{2} = v_a\)。
结合归一化：\(3v_a = 1\)，即 \(v_a = \frac{1}{3}\)。
均衡值： \[\boxed{v_a = v_b = v_c = \frac{1}{3}}\]
2.2 均衡验证
应用一次更新规则：
- \(a\) 接收：\(b\) 的全部 PR = \(\frac{1}{3}\) → \(v'_a = \frac{1}{3}\) ✓
- \(b\) 接收：\(a\) 的一半 \(\frac{1}{6}\) + \(c\) 的一半 \(\frac{1}{6}\) → \(v'_b = \frac{1}{3}\) ✓
- \(c\) 接收：\(a\) 的一半 \(\frac{1}{6}\) + \(c\) 的一半 \(\frac{1}{6}\) → \(v'_c = \frac{1}{3}\) ✓
三个值均未改变 → 确实是均衡值。
2.3 Figure 1(b)：移除 \(b \to a\) 后
关键变化：\(b\) 失去唯一的出链 → \(b\) 变为死端（Dead End）。
按照 Easley-Kleinberg 约定："若一页面无出链，则将自身 PR 全部传给自己"。
新的转移矩阵列（列 = 源节点，行 = 目标节点）： \[M = \begin{pmatrix} 0 & 0 & 0 \\ 1/2 & 1 & 1/2 \\ 1/2 & 0 & 1/2 \end{pmatrix}\]
（列序 \(a, b, c\)；\(b\) 列为 \((0, 1, 0)^T\) 表示"传给自己"）
均衡方程： \[v_a = 0\] \[v_b = \frac{v_a}{2} + v_b + \frac{v_c}{2}\] \[v_c = \frac{v_a}{2} + \frac{v_c}{2}\]
求解：
由 \(v_a = 0\)：代入第三式 \(v_c = \frac{v_c}{2}\)，得 \(v_c = 0\)。
由归一化：\(v_b = 1 - 0 - 0 = 1\)。
均衡值： \[\boxed{v_a = 0,\quad v_b = 1,\quad v_c = 0}\]
2.4 现象解释
- \(a\) 无人指向 → PR 被"耗尽"为 0
- \(c\) 虽有自环，但也指向 \(b\)；PR 逐步流失到 \(b\)
- \(b\) 作为死端"吸收"所有 PR → 最终全部聚集
这是基本 PageRank 的固有缺陷：少数结构（死端/陷阱）会"吸走"整个网络的 PR。Scaled PageRank（见练习 3）通过引入"随机跳转"解决此问题。
三、练习 2：均衡值验证
3.1 Figure 2(a)：六节点对称图
图结构（节点 \(\{A, B, C, D, E, G\}\)）：
边集（根据图中箭头）： - \(A \to D\)，\(A \to G\) - \(D \to B\)，\(G \to C\) - \(B \to E\)，\(C \to E\) - \(E \to A\)
出度： | 节点 | 出度 | 出链目标 | |------|------|----------| | \(A\) | 2 | \(D, G\) | | \(B\) | 1 | \(E\) | | \(C\) | 1 | \(E\) | | \(D\) | 1 | \(B\) | | \(E\) | 1 | \(A\) | | \(G\) | 1 | \(C\) |
提议值：\(v_A = v_E = \frac{1}{4}\)，\(v_B = v_C = v_D = v_G = \frac{1}{8}\)。
验证 \(v = Mv\)：
\[v_A = v_E = \frac{1}{4} \quad ✓\]
\[v_D = \frac{v_A}{2} = \frac{1}{8} \quad ✓\]
\[v_G = \frac{v_A}{2} = \frac{1}{8} \quad ✓\]
\[v_B = v_D = \frac{1}{8} \quad ✓\]
\[v_C = v_G = \frac{1}{8} \quad ✓\]
\[v_E = v_B + v_C = \frac{1}{8} + \frac{1}{8} = \frac{1}{4} \quad ✓\]
总和验证：\(\frac{1}{4} + 4 \times \frac{1}{8} + \frac{1}{4} = \frac{1}{4} + \frac{1}{2} + \frac{1}{4} = 1\) ✓
结论：✅ 提议值是正确的均衡值。
结构洞见：这是一个"双层菱形"结构——\(A\) 将 PR 均分到左右两臂 (\(A \to D \to B \to E\) 与 \(A \to G \to C \to E\))，两臂在 \(E\) 合流，再回到 \(A\)。对称性保证了 \(D=G\)、\(B=C\)。
3.2 Figure 2(b)：六节点图
图结构（节点 \(\{A, B, C, D, E, F\}\)）：
边集（根据图中箭头）： - \(A \to C\)，\(A \to D\) - \(B \to D\)，\(B \to E\) - \(C \to D\)，\(C \to F\) - \(D \to F\) - \(E \to D\)，\(E \to F\) - \(F \to A\)，\(F \to B\)
出度： | 节点 | 出度 | 出链目标 | |------|------|----------------| | \(A\) | 2 | \(C, D\) | | \(B\) | 2 | \(D, E\) | | \(C\) | 2 | \(D, F\) | | \(D\) | 1 | \(F\) | | \(E\) | 2 | \(D, F\) | | \(F\) | 2 | \(A, B\) |
提议值：\(v_A = v_B = 0.15\)，\(v_C = v_E = 0.10\)，\(v_D = 0.20\)，\(v_F = 0.30\)。
逐项验证 \(v = Mv\)：
- \(v_A = \frac{v_F}{2} = \frac{0.30}{2} = 0.15\) ✓
- \(v_B = \frac{v_F}{2} = 0.15\) ✓
- \(v_C = \frac{v_A}{2} = \frac{0.15}{2} = 0.075\) ❌ （提议值 \(0.10\)）
\(C\) 不满足均衡条件！
结论：❌ 提议值不是正确的均衡值。
3.3 求解正确的均衡值
建立完整方程组：
\[v_A = \frac{v_F}{2}\]
\[v_B = \frac{v_F}{2}\]
\[v_C = \frac{v_A}{2}\]
\[v_D = \frac{v_A}{2} + \frac{v_B}{2} + \frac{v_C}{2} + \frac{v_E}{2}\]
\[v_E = \frac{v_B}{2}\]
\[v_F = \frac{v_C}{2} + v_D + \frac{v_E}{2}\]
代入消元：
\(v_A = v_B = \frac{v_F}{2}\)
\(v_C = \frac{v_A}{2} = \frac{v_F}{4}\)
\(v_E = \frac{v_B}{2} = \frac{v_F}{4}\)
\(v_D = \frac{v_F}{4} + \frac{v_F}{4} + \frac{v_F}{8} + \frac{v_F}{8} = \frac{v_F}{2} + \frac{v_F}{4} = \frac{3v_F}{4}\)
验证 \(v_F\) 方程： \[v_F = \frac{v_C}{2} + v_D + \frac{v_E}{2} = \frac{v_F}{8} + \frac{3v_F}{4} + \frac{v_F}{8} = \frac{v_F}{4} + \frac{3v_F}{4} = v_F \quad ✓\]
系统自洽，利用归一化条件求 \(v_F\)： \[v_A + v_B + v_C + v_D + v_E + v_F = 1\]
\[\frac{v_F}{2} + \frac{v_F}{2} + \frac{v_F}{4} + \frac{3v_F}{4} + \frac{v_F}{4} + v_F = 1\]
\[v_F\left(1 + \frac{1}{4} + \frac{3}{4} + \frac{1}{4} + 1\right) = 1\]
\[v_F \cdot \frac{13}{4} = 1 \quad \Rightarrow \quad v_F = \frac{4}{13}\]
正确的均衡 PageRank 值：
\[\boxed{v_A = v_B = \frac{2}{13}, \quad v_C = v_E = \frac{1}{13}, \quad v_D = \frac{3}{13}, \quad v_F = \frac{4}{13}}\]
数值对比：
| 节点 | 提议值 | 正确值 | 十进制 | 差异 |
|---|---|---|---|---|
| A | 0.15 | \(2/13\) | ≈ 0.154 | +0.004 |
| B | 0.15 | \(2/13\) | ≈ 0.154 | +0.004 |
| C | 0.10 | \(1/13\) | ≈ 0.077 | −0.023 |
| D | 0.20 | \(3/13\) | ≈ 0.231 | +0.031 |
| E | 0.10 | \(1/13\) | ≈ 0.077 | −0.023 |
| F | 0.30 | \(4/13\) | ≈ 0.308 | +0.008 |
注意：提议值虽然总和为 1，但不满足 \(v = Mv\)。特别是 \(v_C = 0.10\) 远偏离正确的 \(0.077\)。
四、练习 3：Scaled PageRank 值（\(\alpha = 4/5\)）
4.1 问题设置
回到 Figure 1(b)（即 \(b\) 为死端的图），计算 \(\alpha = \frac{4}{5}\) 的 Scaled PageRank。
网络参数：\(n = 3\)，\(\alpha = 4/5\)，\(1 - \alpha = 1/5\)。
每节点跳转值：\(\frac{1-\alpha}{n} = \frac{1/5}{3} = \frac{1}{15}\)。
4.2 Scaled 更新方程
\[v'_i = \alpha \cdot (Mv)_i + \frac{1-\alpha}{n}\]
具体写出：
\[v_a = \alpha \cdot 0 + \frac{1}{15} = \frac{1}{15}\]
\[v_b = \alpha \left( \frac{v_a}{2} + v_b + \frac{v_c}{2} \right) + \frac{1}{15}\]
\[v_c = \alpha \left( \frac{v_a}{2} + \frac{v_c}{2} \right) + \frac{1}{15}\]
4.3 逐步求解
（1）先求 \(v_a\)： \[v_a = \frac{1}{15}\]
（2）求 \(v_c\)（只与 \(v_a, v_c\) 相关）：
\[v_c = \frac{4}{5}\left(\frac{1}{30} + \frac{v_c}{2}\right) + \frac{1}{15}\]
\[v_c = \frac{4}{150} + \frac{2}{5}v_c + \frac{1}{15}\]
\[v_c = \frac{4}{150} + \frac{10}{150} + \frac{2}{5}v_c\]
\[v_c - \frac{2}{5}v_c = \frac{14}{150}\]
\[\frac{3}{5}v_c = \frac{7}{75}\]
\[v_c = \frac{7}{75} \cdot \frac{5}{3} = \frac{35}{225} = \frac{7}{45}\]
（3）由归一化求 \(v_b\)：
\[v_b = 1 - v_a - v_c = 1 - \frac{1}{15} - \frac{7}{45} = \frac{45 - 3 - 7}{45} = \frac{35}{45} = \frac{7}{9}\]
4.4 验证 \(v_b\)
\[v_b = \frac{4}{5}\left(\frac{v_a}{2} + v_b + \frac{v_c}{2}\right) + \frac{1}{15}\]
代入 \(v_a = \frac{1}{15}\)，\(v_c = \frac{7}{45}\)，\(v_b = \frac{7}{9}\)：
\[\frac{v_a}{2} = \frac{1}{30}, \quad \frac{v_c}{2} = \frac{7}{90}\]
通分到 \(/90\)： \[\frac{v_a}{2} = \frac{3}{90}, \quad v_b = \frac{70}{90}, \quad \frac{v_c}{2} = \frac{7}{90}\]
\[\frac{v_a}{2} + v_b + \frac{v_c}{2} = \frac{3 + 70 + 7}{90} = \frac{80}{90} = \frac{8}{9}\]
\[v_b = \frac{4}{5} \cdot \frac{8}{9} + \frac{1}{15} = \frac{32}{45} + \frac{3}{45} = \frac{35}{45} = \frac{7}{9} \quad ✓\]
4.5 Scaled PageRank 最终值
\[\boxed{v_a = \frac{1}{15}, \quad v_b = \frac{7}{9} = \frac{35}{45}, \quad v_c = \frac{7}{45}}\]
十进制： - \(v_a \approx 0.067\) - \(v_b \approx 0.778\) - \(v_c \approx 0.156\)
4.6 对比基本 PageRank
| 节点 | Basic PR | Scaled PR (\(\alpha = 4/5\)) |
|---|---|---|
| \(a\) | 0 | \(1/15 \approx 0.067\) |
| \(b\) | 1 | \(7/9 \approx 0.778\) |
| \(c\) | 0 | \(7/45 \approx 0.156\) |
观察与解释： 1. Basic PR 下 \(b\) 吸收了全部 PR，\(a\) 和 \(c\) 被"饿死"为 0 2. Scaled PR 通过随机跳转机制，让每个节点至少保留 \(1/15\) 的基础流量 3. \(b\) 仍然最高（作为"汇"），但不再独占；\(c\) 由于自环得以保留更多 PR；\(a\) 由于无入链仍最低 4. \(\alpha\) 越小，越接近均匀分布（\(1/n\)）；\(\alpha\) 越大，越接近基本 PageRank
五、综合总结
5.1 关键公式
| 类型 | 公式 |
|---|---|
| Basic Update Rule | \(v' = Mv\)，死端"传给自己" |
| Equilibrium Condition | \(v = Mv\) 且 \(\sum v_i = 1\) |
| Scaled Update Rule | \(v' = \alpha M v + \frac{1-\alpha}{n}\mathbf{e}\) |
5.2 验证均衡值的标准流程
- 确定边结构：读图列出出度和出链目标
- 写转移矩阵：列 = 源节点，每列和为 1
- 建立方程 \(v = Mv\)
- 代入提议值：逐项检验是否相等
- 若失败：联立求解，用归一化定唯一解
5.3 死端与陷阱的对策
- Basic PageRank 对死端/陷阱敏感：PR 被少数节点吸收
- Scaled PageRank 引入随机跳转：所有节点都保留至少 \((1-\alpha)/n\) 的流量
- 实际搜索引擎通常取 \(\alpha = 0.85\)（即 \(s = 0.85\)）
5.4 与 HITS 对比
| 特性 | PageRank | HITS |
|---|---|---|
| 核心概念 | 单一重要性分数 | 权威 + 中枢双分数 |
| 更新模型 | 流体/随机游走 | 相互递归 |
| 死端处理 | 需 Scaled 修正 | 无此问题 |
| 查询相关 | 查询无关（预计算） | 查询相关（原始版本） |
| 收敛性 | 强连通或 Scaled 时保证 | 矩阵 \(LL^T\) 保证 |
六、术语表
| 中文术语 | English Term | 简要说明 |
|---|---|---|
| 基本 PageRank | Basic PageRank | 最简单的 PageRank 定义，无缩放因子 |
| 均衡 PageRank | Equilibrium PageRank | 满足 \(v = Mv\) 的稳定分布 |
| 缩放 PageRank | Scaled PageRank | 引入随机跳转概率的 PageRank |
| 缩放因子 | Scaling Factor \(\alpha\) / \(s\) | 跟随链接的概率，\(1-\alpha\) 为随机跳转 |
| 转移矩阵 | Transition Matrix \(M\) | 描述 PR 流动的列随机矩阵 |
| 列随机矩阵 | Column-Stochastic Matrix | 每列之和为 1 的非负矩阵 |
| 死端 | Dead End | 无出链的节点，会吸走 PR |
| 自环陷阱 | Spider Trap | 有出链但永远回不到图外的子图 |
| 随机跳转 | Teleportation / Random Jump | Scaled PR 中以 \(1-\alpha\) 概率跳到随机节点 |
| 主特征向量 | Principal Eigenvector | 对应特征值 1 的向量，即均衡 PR |
| 出度 | Out-degree | 节点发出的链接数 |
| 归一化 | Normalization | 让所有 PR 之和为 1 |
| 均匀分布 | Uniform Distribution | 每节点 \(1/n\)，\(\alpha \to 0\) 时的极限 |
文档版本：2026-04-16 对应教材：Easley & Kleinberg, Networks, Crowds, and Markets, 第 14.3 节