PageRank 与幂迭代：图上的马尔可夫链

回顾 Art. 14 算子全景中的两条子线：

• 子线 A（时序）：马尔可夫链 → HMM → Kalman → SSM
• 子线 B（图/空间）：PageRank → 随机游走 → Kernel → Laplacian → GNN

PageRank 同时属于两条子线——它既是一个马尔可夫链（时序演化直到稳态），又是定义在图结构上的算子（每条边代表一个超链接）。理解 PageRank 就是理解”图上的马尔可夫链”，它是两条线交汇的桥梁。

为什么 PageRank 重要？

1998 年，还在斯坦福读博的 Larry Page 和 Sergey Brin 提出了 PageRank 算法（Brin & Page, 1998），用一个简洁的数学模型回答了一个当时无人能优雅解决的问题：互联网上的网页，哪些更”重要”？

他们的核心洞察是：

一个网页的重要性，由链接到它的网页的重要性决定。

这个递归定义听起来像是循环论证——要知道 A 的重要性就得先知道 B 的重要性，而 B 的重要性又取决于 A。但 Page 和 Brin 意识到，这个递归恰好可以用马尔可夫链的稳态分布来求解。互联网是一个有向图，网页是节点，超链接是边；在这个图上定义一个随机游走（random walk），其稳态分布就是每个网页的 PageRank 分数。

而求解稳态分布的方法，就是 Part 1 全景图中提到的幂迭代（power iteration）——反复用矩阵乘以向量，直到收敛。

从矩阵数学的角度，PageRank 展示了三个核心概念的统一：

• 马尔可夫链的稳态（Art. 15 马尔可夫链）：PageRank 就是带 damping 的马尔可夫链的稳态分布
• 幂迭代法：反复乘矩阵 = 信息在图上传播
• 收敛性与谱隙：收敛速度由第二大特征值 $|\lambda_2|$ 决定，与 Art. 15 的谱间隙理论一致

从直觉出发：随机冲浪者模型

想象一个”随机冲浪者”（random surfer）在互联网上浏览网页。他的行为规则很简单：

1. 在当前网页上，随机点击一个出链（outlink）——每个链接被点击的概率相等
2. 偶尔（以概率 $1 - \alpha$）感到无聊，直接跳到互联网上的一个随机网页（与链接结构无关）

这就是 PageRank 的随机冲浪者模型（random surfer model）。参数 $\alpha \in (0,1)$ 称为阻尼因子（damping factor），Brin & Page 原始论文中取 $\alpha = 0.85$。

经过无穷多步之后，冲浪者在各个网页上的”停留概率”就是该网页的 PageRank 分数。直觉上：被很多重要网页链接的网页，冲浪者更容易到达，所以 PageRank 更高。

为什么需要阻尼因子？

不加阻尼（$\alpha = 1$）会遇到两个致命问题：

问题一：Dangling nodes（悬空节点）。有些网页没有出链（比如 PDF 文件）。随机冲浪者到达这样的页面后就”卡住”了——没有链接可以点击。对应的转移矩阵中，这些节点对应的行全为零——不再是行随机矩阵，马尔可夫链的理论不适用。

问题二：Spider traps（蜘蛛陷阱）。如果一组网页只互相链接，不指向外部，冲浪者一旦进入就出不来。这些节点会”吸收”所有 PageRank 值，而其他节点的分数趋向零。从马尔可夫链的角度看，这对应的链是可约的（reducible）——违反了 Perron-Frobenius 定理的不可约性条件，稳态分布可能不唯一。

阻尼因子 $\alpha < 1$ 同时解决了这两个问题：以概率 $1 - \alpha$ 的”随机跳转”保证了冲浪者可以从任意网页到达任意其他网页——这使得转移矩阵的每个元素都严格为正，从而保证了不可约性和非周期性。由 Perron-Frobenius 定理，稳态分布存在且唯一。

严格定义：Google 矩阵

基本设定

设互联网有 $n$ 个网页。定义：

• 超链接矩阵 $H \in \mathbb{R}^{n \times n}$：如果网页 $j$ 有 $L(j)$ 个出链，且其中一个指向网页 $i$，则 $H_{ij} = 1/L(j)$；否则 $H_{ij} = 0$。

注意 $H$ 是列随机的（column stochastic）——如果网页 $j$ 不是 dangling node，则 $H$ 的第 $j$ 列之和为 1。这里我们用列随机而非 Art. 15 中的行随机，是因为 PageRank 中的约定是 $\mathbf{x}$ 为列向量，迭代公式为 $\mathbf{x} \leftarrow M\mathbf{x}$（左乘矩阵），而非 $\boldsymbol{\pi} \leftarrow \boldsymbol{\pi}P$（右乘矩阵）。两种约定是等价的——列随机矩阵 $M$ 对应 Art. 15 中行随机矩阵 $P$ 的转置。

符号约定：本文中 $\mathbf{x} \in \mathbb{R}^n$ 始终是列向量，$x_i$ 表示网页 $i$ 的 PageRank 分数。

处理 dangling nodes

对于 dangling node $j$（$L(j) = 0$），$H$ 的第 $j$ 列全为零。一种标准处理是将这些零列替换为均匀分布 $\frac{1}{n}\mathbf{1}$——即冲浪者到达 dangling node 后等概率跳转到任意网页。定义修正后的矩阵：

$S = H + \frac{1}{n}\mathbf{1}\mathbf{d}^T$

其中 $\mathbf{d} \in \mathbb{R}^n$ 是指示向量，$d_j = 1$ 当且仅当网页 $j$ 是 dangling node。$S$ 是列随机矩阵——每列之和为 1。

Google 矩阵

最终的 Google 矩阵（Google Matrix）$M$ 加入阻尼因子：

$M = \alpha S + (1 - \alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T$

逐项理解：

• $\alpha S$：以概率 $\alpha$ 按链接结构转移（follow a link）
• $(1 - \alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T$：以概率 $1 - \alpha$ 随机跳转到任意网页（teleport）
• $\frac{1}{n}\mathbf{1}\mathbf{1}^T$：这是一个 $n \times n$ 的矩阵，每个元素都是 $1/n$——均匀分布

下图展示了 Google 矩阵的构建——链接跟随和随机跳转两个分量的叠加，以及为什么这个设计保证了 Perron-Frobenius 定理的条件。

$M$ 的关键性质：

1. 列随机：$M$ 的每列之和为 $\alpha \cdot 1 + (1 - \alpha) \cdot 1 = 1$ ✓
2. 严格正：因为 $(1 - \alpha)/n > 0$，$M$ 的每个元素至少为 $(1-\alpha)/n > 0$ ✓
3. 由 Perron-Frobenius 定理：唯一的稳态分布存在，所有特征值的模严格小于 1（除了 $\lambda_1 = 1$）

PageRank 向量的定义

PageRank 向量 $\mathbf{x}^*$ 是 Google 矩阵 $M$ 的主特征向量（dominant eigenvector），对应特征值 $\lambda_1 = 1$：

$M\mathbf{x}^* = \mathbf{x}^*$

满足归一化条件 $\sum_{i=1}^{n} x^*_i = 1$，$x^*_i \geq 0$。

这与 Art. 15 的稳态分布完全一致（只是从行向量/行随机矩阵的约定切换到了列向量/列随机矩阵的约定）。PageRank 就是 Google 矩阵定义的马尔可夫链的稳态分布。

幂迭代法：反复乘矩阵就是传播信息

算法

幂迭代（power iteration）是求解 PageRank 的核心算法。它直接对应随机冲浪者的行为——每一步乘矩阵 $M$ 就是冲浪者走一步。

算法：幂迭代求 PageRank

1. 初始化：$\mathbf{x}_0 = \frac{1}{n}\mathbf{1}$（均匀分布）
2. 迭代：$\mathbf{x}_{k+1} = M\mathbf{x}_k$
3. 终止：当 $\|\mathbf{x}_{k+1} - \mathbf{x}_k\|_1 < \epsilon$ 时停止

由于 $M$ 是列随机的，每一步迭代自动保持 $\sum_i (x_{k})_i = 1$——不需要额外归一化。

为什么幂迭代有效？

回忆 Art. 15 马尔可夫链中的核心结论：设 $M$ 可对角化为 $M = Q\Lambda Q^{-1}$，则：

$M^k = Q\Lambda^k Q^{-1}$

将初始向量 $\mathbf{x}_0$ 在特征基下展开：$\mathbf{x}_0 = c_1\mathbf{q}_1 + c_2\mathbf{q}_2 + \cdots + c_n\mathbf{q}_n$，其中 $\mathbf{q}_i$ 是 $M$ 的第 $i$ 个特征向量。则：

$\mathbf{x}_k = M^k\mathbf{x}_0 = c_1\lambda_1^k\mathbf{q}_1 + c_2\lambda_2^k\mathbf{q}_2 + \cdots + c_n\lambda_n^k\mathbf{q}_n$

因为 $\lambda_1 = 1$ 且 $|\lambda_i| < 1$ 对所有 $i \geq 2$：

$\mathbf{x}_k \xrightarrow{k \to \infty} c_1\mathbf{q}_1 = \mathbf{x}^*$

其中 $\mathbf{q}_1$ 是对应 $\lambda_1 = 1$ 的特征向量（即 PageRank 向量）。所有非稳态分量指数衰减消失，只有稳态分量存活。

下图直观展示了这个过程——随着迭代步数 $k$ 增加，只有 $\lambda_1 = 1$ 对应的分量（绿色）保持不变，其余分量按各自的 $|\lambda_i|^k$ 快速衰减至零。

直觉：信息传播

每一步 $\mathbf{x}_{k+1} = M\mathbf{x}_k$ 的含义是：

$x_{k+1,i} = \alpha \sum_{j \to i} \frac{x_{k,j}}{L(j)} + \frac{1-\alpha}{n}$

即网页 $i$ 在第 $k+1$ 步的 PageRank 等于：

• 所有指向 $i$ 的网页 $j$，各自把自己当前的 PageRank 分数 $x_{k,j}$ 均匀分配给所有出链，$i$ 收到的份额之和（乘以 $\alpha$）
• 加上一个”保底”的均匀分数 $(1-\alpha)/n$（随机跳转贡献）

这就是”信息传播”——每一步矩阵乘法，PageRank 分数沿着链接结构流动。高入链、被重要网页链接的网页，汇聚更多的分数。

数值例子：4 节点手算

考虑一个 4 个网页的小型网络：

• 网页 1 链接到 2 和 3
• 网页 2 链接到 3
• 网页 3 链接到 1
• 网页 4 链接到 1 和 3

取 $\alpha = 0.85$。

第一步：构建超链接矩阵 $H$

$H$ 是列随机的，$H_{ij} = 1/L(j)$ 表示从 $j$ 到 $i$ 的转移概率：

• 网页 1 有 2 个出链（→2, →3）：$H_{21} = H_{31} = 1/2$
• 网页 2 有 1 个出链（→3）：$H_{32} = 1$
• 网页 3 有 1 个出链（→1）：$H_{13} = 1$
• 网页 4 有 2 个出链（→1, →3）：$H_{14} = H_{34} = 1/2$

$H = \begin{bmatrix} 0 & 0 & 1 & 1/2 \\ 1/2 & 0 & 0 & 0 \\ 1/2 & 1 & 0 & 1/2 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

验证列和：第 1 列 $0 + 1/2 + 1/2 + 0 = 1$ ✓，第 2 列 $0 + 0 + 1 + 0 = 1$ ✓，第 3 列 $1 + 0 + 0 + 0 = 1$ ✓，第 4 列 $1/2 + 0 + 1/2 + 0 = 1$ ✓。没有 dangling node，$S = H$。

第二步：构建 Google 矩阵 $M$

$M = 0.85 H + 0.15 \cdot \frac{1}{4}\mathbf{1}\mathbf{1}^T = 0.85 H + 0.0375 \cdot \mathbf{1}\mathbf{1}^T$

$M = \begin{bmatrix} 0.0375 & 0.0375 & 0.8875 & 0.4625 \\ 0.4625 & 0.0375 & 0.0375 & 0.0375 \\ 0.4625 & 0.8875 & 0.0375 & 0.4625 \\ 0.0375 & 0.0375 & 0.0375 & 0.0375 \end{bmatrix}$

验证列和：第 1 列 $0.0375 + 0.4625 + 0.4625 + 0.0375 = 1$ ✓。所有元素正 ✓。

第三步：幂迭代

从均匀分布出发 $\mathbf{x}_0 = (0.25, 0.25, 0.25, 0.25)^T$：

第 1 步：$\mathbf{x}_1 = M\mathbf{x}_0$

$x_{1,1} = 0.0375(0.25) + 0.0375(0.25) + 0.8875(0.25) + 0.4625(0.25) = 0.3563$ $x_{1,2} = 0.4625(0.25) + 0.0375(0.25) + 0.0375(0.25) + 0.0375(0.25) = 0.1438$ $x_{1,3} = 0.4625(0.25) + 0.8875(0.25) + 0.0375(0.25) + 0.4625(0.25) = 0.4625$ $x_{1,4} = 0.0375(0.25) + 0.0375(0.25) + 0.0375(0.25) + 0.0375(0.25) = 0.0375$

$\mathbf{x}_1 \approx (0.3563, 0.1438, 0.4625, 0.0375)^T$

第 2 步：$\mathbf{x}_2 = M\mathbf{x}_1$

$x_{2,1} = 0.0375(0.3563) + 0.0375(0.1438) + 0.8875(0.4625) + 0.4625(0.0375) \approx 0.4466$

$x_{2,2} = 0.4625(0.3563) + 0.0375(0.1438) + 0.0375(0.4625) + 0.0375(0.0375) \approx 0.1889$

$x_{2,3} = 0.4625(0.3563) + 0.8875(0.1438) + 0.0375(0.4625) + 0.4625(0.0375) \approx 0.3270$

$x_{2,4} = 0.0375(0.3563) + 0.0375(0.1438) + 0.0375(0.4625) + 0.0375(0.0375) = 0.0375$

$\mathbf{x}_2 \approx (0.4466, 0.1889, 0.3270, 0.0375)^T$

继续迭代（省略计算细节）：

$k$	$x_1$	$x_2$	$x_3$	$x_4$	$\|\mathbf{x}_k - \mathbf{x}_{k-1}\|_1$
0	0.2500	0.2500	0.2500	0.2500	—
1	0.3563	0.1438	0.4625	0.0375	0.638
2	0.4466	0.1889	0.3270	0.0375	0.271
3	0.3314	0.2273	0.4038	0.0375	0.230
…	…	…	…	…	…
收敛	0.3797	0.1989	0.3839	0.0375	< 10⁻⁶

解读：

• 网页 3 的 PageRank 最高（0.384）——它被网页 1、2、4 三个网页链接
• 网页 1 紧随其后（0.380）——它只被网页 3 和 4 链接，但网页 3 的 PageRank 很高，“传递”了高分数
• 网页 4 的 PageRank 最低（0.038）——没有任何网页链接到它，仅靠随机跳转获得 $(1-\alpha)/n = 0.0375$

可视化：PageRank 幂迭代

下面的交互组件展示了一个 6 节点有向图上的 PageRank 幂迭代。点击播放或逐步前进，观察 PageRank 分数如何从均匀分布逐步收敛到稳态。你还可以调节阻尼因子 $\alpha$，观察它如何影响收敛速度和最终分布。

PageRank 幂迭代动画

◀播放▶重置

t =0

阻尼 α =0.85

节点大小和填充高度反映当前 PageRank 分数。点击 ▶ 逐步观察分数如何从均匀分布收敛到稳态。调节 α 观察阻尼因子的影响。

探索建议：

1. 默认图：观察哪些节点的 PageRank 最高——它们是被多个节点链接的”枢纽”
2. 调低 $\alpha$（如 0.5）：随机跳转概率增大，PageRank 分布趋向均匀——链接结构的影响被稀释
3. 调高 $\alpha$（如 0.99）：几乎完全依赖链接结构，收敛变慢——收敛步数与 $\alpha$ 的关系将在下一节分析
4. 观察收敛速度：底部显示的 $\Delta$(L1 距离) 的衰减速率

收敛性分析：与谱隙的关系

收敛速率

幂迭代的收敛速率由 Google 矩阵 $M$ 的第二大特征值 $|\lambda_2|$ 决定。在 Art. 15 马尔可夫链中我们已经建立了核心结论：

$\|\mathbf{x}_k - \mathbf{x}^*\| \sim |\lambda_2|^k$

谱隙（spectral gap）$\gamma = 1 - |\lambda_2|$ 越大，收敛越快。每一步迭代，误差乘以 $|\lambda_2|$——要使误差从初始值衰减到 $\epsilon$，需要大约：

$k \approx \frac{\ln(1/\epsilon)}{\ln(1/|\lambda_2|)} \approx \frac{\ln(1/\epsilon)}{1 - |\lambda_2|} = \frac{\ln(1/\epsilon)}{\gamma}$

步。（最后一个近似利用了 $\ln(1/x) \approx 1 - x$ 当 $x$ 接近 1 时。）

$\alpha$ 与 $|\lambda_2|$ 的关系

对于 Google 矩阵 $M = \alpha S + (1-\alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T$，有一个关键的谱性质（Langville & Meyer, 2004）：

命题：如果 $S$ 的特征值为 $1 = \mu_1, \mu_2, \ldots, \mu_n$（$|\mu_i| \leq 1$），则 $M$ 的特征值为：

$\lambda_1 = 1, \quad \lambda_i = \alpha \mu_i \quad (i = 2, 3, \ldots, n)$

证明思路：$M = \alpha S + (1-\alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T$。对于 $S$ 的稳态特征向量 $\mathbf{q}_1$（对应 $\mu_1 = 1$），$M\mathbf{q}_1 = \alpha\mathbf{q}_1 + (1-\alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T\mathbf{q}_1 = \alpha\mathbf{q}_1 + (1-\alpha)\mathbf{q}_1 = \mathbf{q}_1$（利用 $\mathbf{1}^T\mathbf{q}_1 = 1$，因为 $\mathbf{q}_1$ 的分量和为 1 且 $\frac{1}{n}\mathbf{1}\cdot n = \mathbf{1}$…更精确地说，$\frac{1}{n}\mathbf{1}(\mathbf{1}^T\mathbf{q}_1) = \frac{1}{n}\mathbf{1} \cdot 1$ 只在 $\mathbf{q}_1$ 分量和为 1 时等于 $\frac{1}{n}\mathbf{1}$，不一定等于 $\mathbf{q}_1$。完整的推导需要更仔细地区分左右特征向量。）对于 $S$ 的其余特征向量 $\mathbf{q}_i$（$i \geq 2$），因为 $\mathbf{1}^T\mathbf{q}_i = 0$（列随机矩阵的非稳态右特征向量分量和为零），所以 $\frac{1}{n}\mathbf{1}\mathbf{1}^T\mathbf{q}_i = \mathbf{0}$，从而 $M\mathbf{q}_i = \alpha S\mathbf{q}_i = \alpha\mu_i\mathbf{q}_i$。$\blacksquare$

这个命题的直接推论：

$|\lambda_2(M)| = \alpha \cdot |\mu_2(S)| \leq \alpha$

因此 Google 矩阵的谱隙至少为 $1 - \alpha$：

$\gamma = 1 - |\lambda_2| \geq 1 - \alpha$

对于 $\alpha = 0.85$，谱隙至少为 $0.15$，意味着每一步迭代误差至少缩减 15%。要使误差衰减到 $\epsilon = 10^{-6}$：

$k \approx \frac{\ln(10^6)}{1 - 0.85} = \frac{13.8}{0.15} \approx 92 \text{ 步}$

实际上，$|\mu_2(S)|$ 通常远小于 1（尤其对于互联网这样的大规模图），所以收敛常常比这个上界快得多。Brin & Page 在原始论文中报告，对于包含 3.22 亿条链接的网页图，大约 50-100 次迭代就足够收敛。

与 Art. 15 的统一视角

对比 Art. 15 马尔可夫链中天气模型的收敛分析：

	Art. 15 天气模型	Art. 18 PageRank
矩阵	行随机矩阵 $P$	列随机 Google 矩阵 $M$
迭代	$\boldsymbol{\pi}_{k+1} = \boldsymbol{\pi}_k P$（行向量右乘）	$\mathbf{x}_{k+1} = M\mathbf{x}_k$（列向量左乘）
稳态	$\boldsymbol{\pi}^*P = \boldsymbol{\pi}^*$	$M\mathbf{x}^* = \mathbf{x}^*$
谱隙	$\gamma = 1 - \|\lambda_2\|$（天气模型中 $= 0.8$）	$\gamma \geq 1 - \alpha$（$\alpha = 0.85$ 时 $\geq 0.15$）
收敛速度	$\sim \|\lambda_2\|^k$	$\sim \|\lambda_2\|^k \leq \alpha^k$

核心一致：无论行随机还是列随机，收敛速度都由谱隙 $\gamma = 1 - |\lambda_2|$ 控制。唯一的差别是约定（行向量 vs 列向量），数学本质完全相同。

幂迭代的一般形式

PageRank 使用的幂迭代法不仅仅是 PageRank 的专属工具——它是求解矩阵主特征值/特征向量的最基本算法之一。

一般幂迭代

给定任意方阵 $A$ 和初始向量 $\mathbf{v}_0$：

1. 迭代：$\tilde{\mathbf{v}}_{k+1} = A\mathbf{v}_k$
2. 归一化：$\mathbf{v}_{k+1} = \tilde{\mathbf{v}}_{k+1} / \|\tilde{\mathbf{v}}_{k+1}\|$
3. 特征值估计：$\lambda \approx \mathbf{v}_{k+1}^T A \mathbf{v}_{k+1}$（Rayleigh 商）

收敛条件：$A$ 有一个严格主特征值 $\lambda_1$（即 $|\lambda_1| > |\lambda_2| \geq \cdots$），且初始向量 $\mathbf{v}_0$ 在 $\lambda_1$ 对应的特征方向上有非零分量。收敛速率 $\sim |\lambda_2/\lambda_1|^k$。

对于 PageRank，$A = M$（Google 矩阵），$\lambda_1 = 1$，所以收敛速率 $\sim |\lambda_2|^k$——不需要额外归一化（因为 $M$ 保持向量的 L1 范数）。

幂迭代 vs 特征分解

为什么 Google 不直接做特征分解（$M = Q\Lambda Q^{-1}$）来求 PageRank？

• 规模：1998 年的互联网约有 1.5 亿网页。$M$ 是 $1.5 \times 10^8 \times 1.5 \times 10^8$ 的矩阵。完整的特征分解是 $O(n^3)$ 的——完全不可行。
• 稀疏性：$M$ 极其稀疏——每个网页平均只有约 10 个出链。一次矩阵-向量乘法 $M\mathbf{x}$ 只需 $O(\text{nnz})$ 时间（$\text{nnz}$ 是非零元素数），远小于 $O(n^2)$。
• 只需一个特征向量：我们只关心 $\lambda_1 = 1$ 对应的主特征向量，不需要完整的谱。幂迭代精确地给出了这个——它自然收敛到主特征方向。

因此，幂迭代是大规模稀疏矩阵求主特征向量的首选方法，时间复杂度为 $O(k \cdot \text{nnz})$，其中 $k$ 是迭代次数。

PageRank 在现代 ML 中的回响

虽然 PageRank 诞生于网页排名，但它的数学结构——在图上定义马尔可夫链，用幂迭代求稳态——在现代 ML 中有广泛的回响。

图神经网络中的消息传递

图神经网络（GNN）的核心操作是消息传递（message passing）——每个节点聚合邻居的特征向量，更新自己的表示。这与 PageRank 的一步迭代 $\mathbf{x}_{k+1} = M\mathbf{x}_k$ 在结构上完全一致。

实际上，APPNP（Personalized PageRank for GNN, Klicpera et al., 2019）直接将 PageRank 的传播机制嵌入了 GNN 架构：

$\mathbf{Z}^{(k+1)} = \alpha \hat{A}\mathbf{Z}^{(k)} + (1-\alpha)\mathbf{H}$

其中 $\hat{A}$ 是归一化邻接矩阵，$\mathbf{H}$ 是节点特征矩阵。这与 PageRank 的 $\mathbf{x}_{k+1} = \alpha S\mathbf{x}_k + (1-\alpha)\frac{1}{n}\mathbf{1}$ 形式相同——阻尼因子变成了”残差连接”（residual connection）的权重。

Art. 22 图扩散/GNN 将深入展开这个连接。

推荐系统

推荐系统中的 Personalized PageRank（PPR）将随机跳转目标从均匀分布改为特定用户的偏好分布，用于衡量图中节点之间的”个性化亲近度”。PPR 是 Pinterest 的推荐引擎 Pixie 的核心算法之一。

知识图谱

在知识图谱补全任务中，基于随机游走的方法（如 PTransE）在实体-关系图上执行类似 PageRank 的信息传播，将”多跳推理”转化为矩阵幂运算。

总结与展望

本文从 PageRank 出发，展示了”图上的马尔可夫链”如何统一时序和图两条子线：

• PageRank = 带 damping 的马尔可夫链稳态：Google 矩阵 $M = \alpha S + (1-\alpha)\frac{1}{n}\mathbf{1}\mathbf{1}^T$ 是严格正的列随机矩阵，Perron-Frobenius 保证唯一稳态
• 幂迭代 = 信息传播：$\mathbf{x}_{k+1} = M\mathbf{x}_k$，每步矩阵乘法让 PageRank 沿链接流动
• 收敛速度由谱隙控制：$|\lambda_2(M)| \leq \alpha$，谱隙 $\gamma \geq 1 - \alpha$，与 Art. 15 的混合时间理论完全一致
• 阻尼因子 $\alpha$ 解决了 dangling nodes 和 spider traps，保证不可约性
• 幂迭代是大规模稀疏矩阵求主特征向量的首选：$O(k \cdot \text{nnz})$，远优于完整特征分解的 $O(n^3)$

下一篇，我们将 PageRank 的思想推广到一般图上的随机游走（random walk）。DeepWalk 和 Node2Vec 通过在图上做随机游走生成节点序列，然后用 Word2Vec（Art. 11 Word2Vec）学习节点嵌入——这是 Part 1 和 Part 2 的一次直接交汇。从”网页排名”到”节点嵌入”，底层数学不变：矩阵乘法就是信息传播。