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 a\)（自环），\(a \to b\)，\(a \to c\) - \(b \to a\)，\(b \to c\) - \(c \to b\) - \(c \to c\)（自环）
出度：
| 节点 | 出度 | 出链目标 |
|---|---|---|
| \(a\) | 3 | \(a, b, c\) |
| \(b\) | 2 | \(a, c\) |
| \(c\) | 2 | \(b, c\) |
建立均衡方程 \(v = Mv\)：
\[v_a = \frac{v_a}{3} + \frac{v_b}{2}\]
\[v_b = \frac{v_a}{3} + \frac{v_c}{2}\]
\[v_c = \frac{v_a}{3} + \frac{v_b}{2} + \frac{v_c}{2}\]
归一化条件：\(v_a + v_b + v_c = 1\)。
求解：
由第一式： \[v_a - \frac{v_a}{3} = \frac{v_b}{2} \quad \Rightarrow \quad \frac{2v_a}{3} = \frac{v_b}{2} \quad \Rightarrow \quad v_b = \frac{4v_a}{3}\]
由第三式： \[v_c - \frac{v_c}{2} = \frac{v_a}{3} + \frac{v_b}{2} \quad \Rightarrow \quad v_c = \frac{2v_a}{3} + v_b\]
代入 \(v_b = \frac{4v_a}{3}\)，得： \[v_c = \frac{2v_a}{3} + \frac{4v_a}{3} = 2v_a\]
结合归一化： \[v_a + \frac{4v_a}{3} + 2v_a = 1 \quad \Rightarrow \quad \frac{13v_a}{3} = 1 \quad \Rightarrow \quad v_a = \frac{3}{13}\]
因此 \(v_b = \frac{4}{13}\)，\(v_c = \frac{6}{13}\)。
均衡值： \[\boxed{v_a = \frac{3}{13},\quad v_b = \frac{4}{13},\quad v_c = \frac{6}{13}}\]
2.2 均衡验证
应用一次更新规则：
- \(a\) 接收：\(a\) 的三分之一 \(\frac{1}{13}\) + \(b\) 的一半 \(\frac{2}{13}\) → \(v'_a = \frac{3}{13}\) ✓
- \(b\) 接收：\(a\) 的三分之一 \(\frac{1}{13}\) + \(c\) 的一半 \(\frac{3}{13}\) → \(v'_b = \frac{4}{13}\) ✓
- \(c\) 接收：\(a\) 的三分之一 \(\frac{1}{13}\) + \(b\) 的一半 \(\frac{2}{13}\) + \(c\) 的一半 \(\frac{3}{13}\) → \(v'_c = \frac{6}{13}\) ✓
三个值均未改变 → 确实是均衡值。
2.3 Figure 1(b)：移除 \(b \to a\) 后
关键变化：移除 \(b \to a\) 后，\(b\) 仍有出链 \(b \to c\)，所以它不是死端（Dead End）。图中 \(\{b,c\}\) 形成闭合部分：PageRank 一旦从 \(a\) 流入 \(b,c\)，就不会再回到 \(a\)。
新的边集： - \(a \to a\)，\(a \to b\)，\(a \to c\) - \(b \to c\) - \(c \to b\)，\(c \to c\)
新的转移矩阵列（列 = 源节点，行 = 目标节点）： \[M = \begin{pmatrix} 1/3 & 0 & 0 \\ 1/3 & 0 & 1/2 \\ 1/3 & 1 & 1/2 \end{pmatrix}\]
（列序 \(a, b, c\)）
均衡方程： \[v_a = \frac{v_a}{3}\] \[v_b = \frac{v_a}{3} + \frac{v_c}{2}\] \[v_c = \frac{v_a}{3} + v_b + \frac{v_c}{2}\]
求解：
由第一式： \[v_a = \frac{v_a}{3} \quad \Rightarrow \quad v_a = 0\]
代入第二式： \[v_b = \frac{v_c}{2}\]
结合归一化： \[v_b + v_c = 1,\quad v_b = \frac{v_c}{2}\]
因此： \[\frac{3v_c}{2} = 1 \quad \Rightarrow \quad v_c = \frac{2}{3},\quad v_b = \frac{1}{3}\]
均衡值： \[\boxed{v_a = 0,\quad v_b = \frac{1}{3},\quad v_c = \frac{2}{3}}\]
2.4 现象解释
- \(a\) 只有自环作为入链，但每轮会把一部分 PR 分给 \(b,c\)；均衡时必须满足 \(v_a = v_a/3\)，所以 \(v_a = 0\)
- \(b,c\) 形成闭合子图：\(b \to c\)，\(c \to b,c\)，PageRank 进入后不会回到 \(a\)
- \(c\) 同时接收 \(b\) 的全部 PR 和自己的部分 PR，因此最终高于 \(b\)
这是基本 PageRank 在非强连通图上的典型现象：PageRank 会集中到闭合连通部分，其他节点可能降为 0。Scaled PageRank（见练习 3）通过引入"随机跳转"解决此问题。
三、练习 2：均衡值验证
3.1 Figure 2(a)：六节点对称图
图结构（节点 \(\{A, B, C, D, E, G\}\)）：
边集（根据图中箭头）： - \(A \to B\)，\(A \to C\) - \(B \to D\)，\(B \to E\) - \(C \to E\)，\(C \to G\) - \(D \to A\)，\(E \to A\)，\(G \to A\)
出度：
| 节点 | 出度 | 出链目标 |
|---|---|---|
| \(A\) | 2 | \(B, C\) |
| \(B\) | 2 | \(D, E\) |
| \(C\) | 2 | \(E, G\) |
| \(D\) | 1 | \(A\) |
| \(E\) | 1 | \(A\) |
| \(G\) | 1 | \(A\) |
提议值：\(v_A = v_E = \frac{1}{4}\)，\(v_B = v_C = v_D = v_G = \frac{1}{8}\)。
验证 \(v = Mv\)：
\[v_B = \frac{v_A}{2} = \frac{1}{8} \quad \text{成立}\]
\[v_C = \frac{v_A}{2} = \frac{1}{8} \quad \text{成立}\]
\[v_D = \frac{v_B}{2} = \frac{1}{16} \ne \frac{1}{8} \quad \text{不成立}\]
因此提议值不是均衡值。
建立完整方程组：
\[v_A = v_D + v_E + v_G\]
\[v_B = \frac{v_A}{2}\]
\[v_C = \frac{v_A}{2}\]
\[v_D = \frac{v_B}{2}\]
\[v_E = \frac{v_B}{2} + \frac{v_C}{2}\]
\[v_G = \frac{v_C}{2}\]
代入消元：
\[v_B = v_C = \frac{v_A}{2}\]
\[v_D = v_G = \frac{v_A}{4}\]
\[v_E = \frac{v_A}{4} + \frac{v_A}{4} = \frac{v_A}{2}\]
利用归一化条件：
\[v_A + \frac{v_A}{2} + \frac{v_A}{2} + \frac{v_A}{4} + \frac{v_A}{2} + \frac{v_A}{4} = 1\]
\[3v_A = 1 \quad \Rightarrow \quad v_A = \frac{1}{3}\]
正确的均衡 PageRank 值：
\[\boxed{v_A = \frac{1}{3},\quad v_B = v_C = v_E = \frac{1}{6},\quad v_D = v_G = \frac{1}{12}}\]
结构洞见：\(A\) 将 PR 均分给 \(B,C\)，\(B,C\) 再向下游分流；\(D,E,G\) 都回到 \(A\)。其中 \(E\) 同时接收 \(B,C\) 的贡献，所以 \(E\) 与 \(B,C\) 同为 \(\frac{1}{6}\)，而 \(D,G\) 只有单侧贡献，各为 \(\frac{1}{12}\)。
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 \text{成立}\]
系统自洽，利用归一化条件求 \(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 \to a\) 后的图），计算 \(\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 \frac{v_a}{3} + \frac{1}{15}\]
\[v_b = \alpha \left( \frac{v_a}{3} + \frac{v_c}{2} \right) + \frac{1}{15}\]
\[v_c = \alpha \left( \frac{v_a}{3} + v_b + \frac{v_c}{2} \right) + \frac{1}{15}\]
4.3 逐步求解
（1）先求 \(v_a\)： \[v_a = \frac{4}{5}\cdot\frac{v_a}{3} + \frac{1}{15}\]
\[v_a - \frac{4v_a}{15} = \frac{1}{15}\]
\[\frac{11v_a}{15} = \frac{1}{15} \quad \Rightarrow \quad v_a = \frac{1}{11}\]
（2）用 \(v_b\) 方程表示 \(v_b\)：
\[v_b = \frac{4}{5}\left(\frac{1}{33} + \frac{v_c}{2}\right) + \frac{1}{15}\]
\[v_b = \frac{4}{165} + \frac{2v_c}{5} + \frac{1}{15}\]
\[v_b = \frac{1}{11} + \frac{2v_c}{5}\]
（3）由归一化求 \(v_c, v_b\)：
\[v_b + v_c = 1 - v_a = \frac{10}{11}\]
代入 \(v_b = \frac{1}{11} + \frac{2v_c}{5}\)：
\[\frac{1}{11} + \frac{2v_c}{5} + v_c = \frac{10}{11}\]
\[\frac{7v_c}{5} = \frac{9}{11} \quad \Rightarrow \quad v_c = \frac{45}{77}\]
\[v_b = \frac{10}{11} - \frac{45}{77} = \frac{25}{77}\]
4.4 验证 \(v_b\)
\[v_b = \frac{4}{5}\left(\frac{v_a}{3} + \frac{v_c}{2}\right) + \frac{1}{15}\]
代入 \(v_a = \frac{1}{11}\)，\(v_c = \frac{45}{77}\)：
\[\frac{v_a}{3} = \frac{1}{33}, \quad \frac{v_c}{2} = \frac{45}{154}\]
通分到 \(/462\)： \[\frac{v_a}{3} = \frac{14}{462}, \quad \frac{v_c}{2} = \frac{135}{462}\]
\[\frac{v_a}{3} + \frac{v_c}{2} = \frac{149}{462}\]
\[v_b = \frac{4}{5}\cdot\frac{149}{462} + \frac{1}{15} = \frac{298}{1155} + \frac{77}{1155} = \frac{375}{1155} = \frac{25}{77} \quad \text{成立}\]
同理验证 \(v_c\)：
\[v_c = \frac{4}{5}\left(\frac{v_a}{3} + v_b + \frac{v_c}{2}\right) + \frac{1}{15}\]
\[\frac{v_a}{3} + v_b + \frac{v_c}{2} = \frac{1}{33} + \frac{25}{77} + \frac{45}{154} = \frac{299}{462}\]
\[v_c = \frac{4}{5}\cdot\frac{299}{462} + \frac{1}{15} = \frac{1196}{2310} + \frac{154}{2310} = \frac{1350}{2310} = \frac{45}{77} \quad \text{成立}\]
4.5 Scaled PageRank 最终值
\[\boxed{v_a = \frac{1}{11}, \quad v_b = \frac{25}{77}, \quad v_c = \frac{45}{77}}\]
十进制： - \(v_a \approx 0.091\) - \(v_b \approx 0.325\) - \(v_c \approx 0.584\)
4.6 对比基本 PageRank
| 节点 | Basic PR | Scaled PR (\(\alpha = 4/5\)) |
|---|---|---|
| \(a\) | 0 | \(1/11 \approx 0.091\) |
| \(b\) | \(1/3 \approx 0.333\) | \(25/77 \approx 0.325\) |
| \(c\) | \(2/3 \approx 0.667\) | \(45/77 \approx 0.584\) |
观察与解释： 1. Basic PR 下 \(a\) 因无法从 \(b,c\) 获得回流而降为 0 2. Scaled PR 通过随机跳转机制，让 \(a\) 重新获得正的 PageRank 3. \(c\) 仍然最高，因为它接收 \(b\) 的全部 PR，同时保留自己的部分 PR 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 节