【统计学习方法死磕系列Ⅱ】PageRank算法

一、引言：Google 的起源算法

1998 年，斯坦福大学的两位博士生 Sergey Brin 和 Larry Page 发表了一篇论文，提出了一个名为 PageRank 的网页排序算法。这个算法后来成为 Google 搜索引擎的核心，两位作者也辍学创办了一家你可能听说过的公司。

PageRank 的核心理念可以用一句话概括：一个网页的重要性，取决于有多少重要网页指向它。这是一种自指的（self-referential）、递归的重要性定义——看似是循环论证，但在数学上却有着严密的基础。

本文将深入 PageRank 的三种等价表示（随机游走、马尔可夫链、特征向量），推导其数学原理，讨论阻尼因子的作用，并介绍若干变体。

二、PageRank 的三种等价视角

2.1 视角一：随机游走模型

想象一个”随机冲浪者”（random surfer）：他从某个网页出发，每一步操作都遵循以下规则：

• 以概率 $d$（$0 < d < 1$，通常 $d = 0.85$）：在当前页面上随机点击一个链接跳转到该链接指向的页面
• 以概率 $1 - d$：感到无聊，随机跳转到互联网上的任意一个页面

经过足够长时间的浏览，这位冲浪者访问每个页面所花的时间比例，就是这个页面的 PageRank 值。

2.2 视角二：马尔可夫链

网页之间的跳转可以建模为一个有限状态马尔可夫链：

• 状态：$N$ 个网页
• 状态转移矩阵 $P \in \mathbb{R}^{N \times N}$：$P_{ij}$ 是从页面 $j$ 跳转到页面 $i$ 的概率

转移矩阵的构造：

步骤 1：构造邻接矩阵的转移版本

$$ A_{ij} = \begin{cases} 1 / L_j & \text{if page } j \text{ links to page } i \\ 0 & \text{otherwise} \end{cases} $$

其中 $L_j$ 是页面 $j$ 的出链数。如果页面 $j$ 没有出链（dangling node），则 $A_{:j} = 1/N$（等概率跳转到所有页面）。

步骤 2：加入阻尼因子

$$ P = d \cdot A + (1 - d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N} $$

其中 $\mathbf{1}$ 是全 1 向量，$\mathbf{1}\mathbf{1}^T / N$ 是均匀跳转矩阵。

PageRank 向量 $\pi$ 就是这个马尔可夫链的平稳分布（stationary distribution）：

$$ \pi = P \pi $$

即 $\pi$ 是 $P$ 的主特征向量（对应特征值 1）。

2.3 视角三：特征向量问题

PageRank 向量 $\pi$ 是转移矩阵 $P$ 对应特征值 1 的特征向量：

$$ P \pi = \pi, \quad \sum_{i=1}^{N} \pi_i = 1 $$

由 Perron-Frobenius 定理，对于素矩阵（primitive matrix）$P$，存在唯一的正平稳分布。

2.4 三种视角的统一

视角	数学形式	直观
随机游走	冲浪者随机浏览	“重要页面被逛得最多”
马尔可夫链	$\pi = P \pi$	平稳分布即 PageRank
特征向量	$\pi$ 是 $P$ 的主特征向量	不变的重要性度量

三、数学推导

3.1 PageRank 的原始定义

Brin 和 Page 的原始公式：

$$ PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)} $$

其中：

• $PR(p_i)$：页面 $p_i$ 的 PageRank 值
• $M(p_i)$：所有链向 $p_i$ 的页面集合
• $L(p_j)$：页面 $p_j$ 的出链数
• $d$：阻尼因子（damping factor），通常取 0.85
• $N$：网页总数

3.2 矩阵形式的推导

定义链接矩阵 $H$：

$$ H_{ij} = \begin{cases} 1 / L_j & \text{if page } j \text{ links to page } i \\ 0 & \text{otherwise} \end{cases} $$

则 PageRank 向量 $\pi$ 满足：

$$ \pi^{(k+1)} = d \cdot H \cdot \pi^{(k)} + \frac{1-d}{N} \cdot \mathbf{1} $$

或者用 $A$（修正后的转移矩阵）和 $P$（完整转移矩阵）：

$$ \pi = P \pi, \quad P = d \cdot A + (1-d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N} $$

3.3 阻尼因子的作用

阻尼因子 $d$ 在 PageRank 中有三个关键作用：

1. 保证收敛：确保 $P$ 是素矩阵（primitive），从而幂迭代一定收敛到唯一的平稳分布
2. 处理悬垂节点（dangling nodes）：没有出链的页面不会”困住”冲浪者
3. 控制收敛速度：$d$ 越小，随机跳转越频繁，收敛越快；$d$ 越大，收敛越慢但更能反映链接结构

$d = 0.85$ 是经验最佳值——它为链接结构提供了足够的权重，同时保证快速收敛。这大致意味着冲浪者平均每点击 5-6 个链接后会跳转到新页面。

3.4 收敛性的数学保证：Perron-Frobenius 定理

PageRank 的收敛性由 Perron-Frobenius 定理严格保证，这是理解 PageRank 数学基础的”灵魂定理”。

Perron-Frobenius 定理（对于正矩阵）：设 $P \in \mathbb{R}^{N \times N}$ 的所有元素 $P_{ij} > 0$（正矩阵）。则：

1. 谱半径 $\rho(P) = 1$ 是 $P$ 的简单特征值（代数重数为 1）

2. 存在唯一的正特征向量 $\pi$（所有分量 $> 0$），满足 $P\pi = \pi$ 且 $\sum_i \pi_i = 1$

3. 所有其他特征值的模严格小于 1：$|\lambda_i| < 1$ 对 $i = 2, \dots, N$

4. 幂迭代收敛：对任意初始正向量 $\pi^{(0)}$，

   $$ \lim_{k \to \infty} P^k \pi^{(0)} = \pi $$

为什么 PageRank 的转移矩阵 $P$ 是正矩阵？

回想 $P = d \cdot A + (1-d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N}$：

• $A$ 可能包含零元素（并非所有页面都相互链接）
• 但 $(1-d) \cdot \frac{\mathbf{1}\mathbf{1}^T}{N}$ 的每一个元素都是 $(1-d)/N > 0$（因为 $d < 1$）
• 因此 $P_{ij} \geq (1-d)/N > 0$，即 $P$ 的所有元素严格为正

这正是阻尼因子 $d < 1$ 的深层数学作用：将可能稀疏的 $A$ 矩阵变为处处为正的 $P$ 矩阵，从而满足了 Perron-Frobenius 定理的前提条件。如果 $d = 1$，$P = A$ 可能不满足正性条件，幂迭代可能在多个特征向量之间振荡而不收敛。

收敛速度的定量分析：

假设 $P$ 的特征值排序为 $1 = \lambda_1 > |\lambda_2| \geq |\lambda_3| \geq \dots$。可以证明：

$$ |\lambda_2| \leq d $$

因此经过 $k$ 次幂迭代后，误差以 $O(d^k)$ 的速度衰减。要达到误差 $\varepsilon$，需要的迭代次数约：

$$ k \approx \frac{\log \varepsilon}{\log d} $$

当 $d = 0.85$ 时，要达到 $\varepsilon = 10^{-8}$：
$$ k \approx \frac{-8}{\log_{10}(0.85)} \approx 114 \text{ 次迭代} $$

在实际的 Google 系统中，通常 50-100 次迭代已经足够获得稳定排序。

四、幂迭代法求解 PageRank

4.1 算法

当 $N$ 为数十亿级别时，直接求解 $P$ 的特征向量是不可行的。PageRank 使用幂迭代法（power iteration）：

Algorithm: Power Iteration for PageRank
----------------------------------------------
Input: adjacency matrix (as sparse representation), 
       damping factor d, tolerance ε
Output: PageRank vector π

1. Initialize π^(0) = (1/N, 1/N, ..., 1/N)
2. k = 1
3. Repeat:
       π^(k+1) = d * A * π^(k) + (1-d) * 1/N
       if ||π^(k+1) - π^(k)||_1 < ε:
           break
       k += 1
4. Return π^(k+1)

4.2 收敛性

幂迭代的收敛速度由次大特征值 $|\lambda_2|$ 决定：

$$ \|\pi^{(k)} - \pi^*\| \approx O(|\lambda_2|^k) $$

对于 PageRank 矩阵 $P = dA + (1-d)\mathbf{1}\mathbf{1}^T/N$，可以证明：

$$ |\lambda_2| \leq d $$

因此，迭代大约 $\frac{\log \varepsilon}{\log d}$ 步后收敛。当 $d = 0.85, \varepsilon = 10^{-8}$ 时，约需 $\frac{-8}{\log_{10}(0.85)} \approx 114$ 次迭代。

4.3 Python 实现

import numpy as np

def pagerank(adj_matrix, d=0.85, tol=1e-8, max_iter=100):
    """
    Compute PageRank using power iteration.
    
    adj_matrix: N x N adjacency matrix (sparse recommended)
    """
    N = adj_matrix.shape[0]
    
    # Compute out-degree for each page
    out_degree = np.sum(adj_matrix, axis=0)
    
    # Build transition matrix A (handle dangling nodes)
    A = np.zeros((N, N))
    for j in range(N):
        if out_degree[j] > 0:
            A[:, j] = adj_matrix[:, j] / out_degree[j]
        else:
            # Dangling node: link to all pages equally
            A[:, j] = 1.0 / N
    
    # Initialize
    pi = np.ones(N) / N
    
    # Power iteration
    for _ in range(max_iter):
        pi_new = d * A @ pi + (1 - d) / N
        
        if np.sum(np.abs(pi_new - pi)) < tol:
            return pi_new
        
        pi = pi_new
    
    return pi

# Example: tiny web of 4 pages
# Page 1 -> Page 2,3
# Page 2 -> Page 3
# Page 3 -> Page 1
# Page 4 -> Page 1,3
adj = np.array([
    [0, 0, 1, 1],
    [1, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0]
])

pr = pagerank(adj)
for i, p in enumerate(pr):
    print(f"Page {i+1}: {p:.4f}")
# Output: Page 3 > Page 1 > Page 2 (Page 4 has no inlinks, PR from teleportation only)

五、PageRank 的变体

5.1 个性化 PageRank（Personalized PageRank）

标准 PageRank 的随机跳转是均匀分布在所有页面上。个性化 PageRank 将跳转分布偏向用户感兴趣的子集：

$$ \pi = d \cdot A \cdot \pi + (1-d) \cdot v $$

其中 $v$ 是用户的个性化向量（$\sum_i v_i = 1$）。例如，$v$ 可以只给用户常访问的页面非零权重。

应用：个性化搜索排序、推荐系统中的相关性排序。

5.2 主题敏感 PageRank（Topic-Sensitive PageRank）

这是个性化 PageRank 的推广。为每个主题（如体育、科技、娱乐等）计算一个 PageRank 向量，查询时根据查询的主题加权组合：

$$ \pi_{\text{query}} = \sum_{t} P(t|\text{query}) \cdot \pi_t $$

5.3 HITS 算法（Hyperlink-Induced Topic Search）

Kleinberg (1999) 提出的 HITS 算法将网页分为两种角色：

• Hub（枢纽）：列出大量优质链接的页面
• Authority（权威）：被大量 Hub 链接的页面

Hub 和 Authority 互相增强：

$$ a(v) = \sum_{u \to v} h(u), \quad h(u) = \sum_{u \to v} a(v) $$

矩阵形式：$a = A^T A a$（$a$ 是 $A^T A$ 的主特征向量），$h = AA^T h$（$h$ 是 $AA^T$ 的主特征向量）。

5.4 TextRank

TextRank（Mihalcea & Tarau, 2004）将 PageRank 的思想推广到自然语言处理。它将词或句子视为图的节点，将共现关系或相似度作为边，用 PageRank 来计算每个节点的重要性。应用包括关键词提取和自动摘要。

# TextRank for keyword extraction
def build_word_graph(words, window=2):
    """Build graph where nodes are words, edges are co-occurrences in window"""
    graph = {}
    for i, w1 in enumerate(words):
        if w1 not in graph:
            graph[w1] = set()
        for j in range(i+1, min(i+window+1, len(words))):
            w2 = words[j]
            graph[w1].add(w2)
            if w2 not in graph:
                graph[w2] = set()
            graph[w2].add(w1)
    return graph

5.5 变体对比

算法	核心创新	适用场景
PageRank	全局重要性 + 随机跳转	网页搜索
Personalized PR	偏向特定用户的跳转	个性化推荐
Topic-Sensitive PR	按主题组合跳转	主题搜索
HITS	Hub/Authority 二分	学术引用分析
TextRank	图上做 PageRank	关键词/句子提取
SimRank	结构相似度	图节点相似度

5.6 学术影响力度量：PageRank 的跨界应用

PageRank 的思想被广泛应用于学术出版领域的影响力评估。一个直接类比是将”论文”视为网页，”引用”视为超链接：

PaperRank（或称为”引用 PageRank”）：

• 节点：每篇论文
• 有向边：论文 A 引用论文 B -> 边从 B 指向 A（被引用的论文获得权重）
• 直觉：被重要论文引用的论文更重要

这与传统的引用计数（citation count）的根本区别在于：**PageRank 区分了引用的”质量”**。被一篇高影响力论文引用远比被一篇普通论文引用更有价值。

类似地，在社交网络分析中：

• TwitterRank：用户被重要用户 @提及 或 retweet，则更重要
• Influence Maximization：用 PageRank 变体找到社交网络中影响力最大的节点集合

在生物信息学中，GeneRank 将基因表达数据与基因-基因交互网络结合，通过 PageRank 式的传播算法发现与疾病相关的关键基因。

5.7 图上的随机游走与混合时间

PageRank 本质上计算的是随机游走的平稳分布。这引出了混合时间（mixing time）的概念——随机游走需要多少步才能”忘记”起始状态并接近平稳分布。

对于 web 图，混合时间的上界约为：

$$ t_{\text{mix}}(\varepsilon) \leq \frac{\log(1/\varepsilon)}{1 - \lambda_2} $$

其中 $\lambda_2 \leq d = 0.85$。这意味着：

• 约 30 步后，冲浪者的位置分布已经接近 PageRank 分布（$0.85^{30} \approx 0.0076$）
• 约 50 步后，初始状态的影响几乎完全消失（$0.85^{50} \approx 0.0003$）

这个性质解释了为什么 PageRank 对 web 图的局部变化具有一定鲁棒性——个别链接的新增/删除只影响局部随机游走行为，全局平稳分布只通过迭代传播受到间接影响。

六、面试高频问题

Q1：为什么 PageRank 可以收敛？阻尼因子 d 为什么重要？

PageRank 的幂迭代收敛由转移矩阵 $P = dA + (1-d)\mathbf{1}\mathbf{1}^T/N$ 的谱性质保证。$P$ 是一个列随机矩阵，且由于 $(1-d)\mathbf{1}\mathbf{1}^T/N$ 的存在，$P$ 的所有元素都严格为正（素矩阵条件）。Perron-Frobenius 定理保证这样的矩阵有唯一的特征值 1（模最大）且对应的特征向量为正。

没有阻尼因子（$d=1$），转移矩阵可能不可约（如果 web 图不连通）或周期性，导致幂迭代不收敛或不唯一。$d < 1$ 是保证数学良好性质的关键。

Q2：幂迭代法需要多少次迭代才能收敛？收敛速度由什么决定？

收敛速度为 $O(d^k)$（$d$ 为阻尼因子，通常 0.85）。以 $d=0.85$ 为例：

• 50 次迭代：误差约为 $0.85^{50} \approx 0.0003$
• 100 次迭代：误差约为 $0.85^{100} \approx 8.7 \times 10^{-8}$

实际 Google 系统中，大约 50-100 次迭代就足够。这百万亿规模的矩阵运算在分布式系统上完成。

Q3：什么是”Dangling Node”问题？如何解决？

Dangling node（悬垂节点）是指没有出链的页面（如 PDF、图片等）。冲浪者到达这样的页面后”无处可去”。

在计算中，悬垂节点会使转移矩阵的对应列全为零，破坏列随机性，导致 PageRank 泄漏（所有 PageRank 值最终趋向于零）。

解决方案：

1. 将悬垂节点的出链视为链向所有页面（包括自己），即 $A_{:j} = \mathbf{1}/N$
2. 先计算无阻尼的 PageRank，再对悬垂节点做特殊处理
3. 直接从 web 图中移除悬垂节点再计算

Q4：PageRank 与 HITS 的区别是什么？

方面	PageRank	HITS
计算范围	全局（离线）	局部（查询相关子图）
角色	单一分数	Hub + Authority 二元
阻尼因子	有	无
计算方式	幂迭代	幂迭代（分别对 $A^TA$ 和 $AA^T$）
查询依赖性	查询无关	查询相关
稳定性	鲁棒	对链接结构变化敏感

Q5：如何将 TextRank 用于自动摘要？

将文档中的每个句子作为图的节点，句子之间的相似度（如 TF-IDF 的余弦相似度或词重叠率）作为边的权重。在加权图上运行 PageRank，得分最高的若干句子被选为摘要。

# Simplified TextRank summarization
def textrank_summarize(sentences, n=3):
    # Build similarity matrix
    N = len(sentences)
    sim = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            if i != j:
                sim[i, j] = cosine_similarity(sentences[i], sentences[j])
    
    # Normalize to stochastic matrix
    for j in range(N):
        if sim[:, j].sum() > 0:
            sim[:, j] /= sim[:, j].sum()
    
    # PageRank
    pr = pagerank(sim, d=0.85)
    
    # Select top n sentences
    top_indices = np.argsort(pr)[::-1][:n]
    return [sentences[i] for i in sorted(top_indices)]

Q6：Personalized PageRank 如何高效计算？naive 方法需要为每个用户算一遍幂迭代吗？

不需要。Personalized PageRank（PPR）可以通过枢纽定理（Hub Decomposition）高效计算。

由于 PPR 向量满足线性关系：

$$ \pi_{\text{PPR}} = (1-d) v + d \cdot A^T \pi_{\text{PPR}} $$

可以展开为：

$$ \pi_{\text{PPR}} = (1-d) \sum_{t=0}^{\infty} d^t (A^T)^t v $$

这表示 PPR 是 $v$ 在随机游走各步上的加权组合。对于给定的用户偏好向量 $v$，有几种高效计算方法：

1. 局部 PPR（近似）：对于每个查询节点，只计算其邻近子图上的 PPR，利用随机游走的局部衰减性质（$d^t$ 快速减小）。实际中通常在数十到数百步后截断。

2. PPR 预计算 + 查询时组合：对于 Topic-Sensitive PageRank，预先计算一组基准 PPR 向量（每个主题一个），查询时按需线性组合。这是 Google 在 2003 年实际使用的策略。

3. FORA 算法（Wang et al., 2017）：结合前向推演（forward push）和随机游走采样，在保证精度下大幅降低计算复杂度。

4. Hub Decomposition：将 PPR 分解为若干个 hub 节点的贡献之和——$v$ 中大部分权重集中在少数节点上时特别有效。

实践中，工业级 PPR 的延迟要求在毫秒级，这意味着必须牺牲一定精度换取速度。这也是为什么搜索引擎的个性化排序在很多年里进展缓慢——PageRank 的精确个性化计算确实是困难问题。

Q7：如果把阻尼因子 d 从 0.85 改为 0.99 会怎样？

两个主要影响：

1. 收敛速度变慢：达到同样精度需要的迭代次数从约 114 次增加到约 1838 次（$k \approx \log(10^{-8}) / \log(0.99$)），计算成本大幅增加。

2. **PageRank 值更”极端”**：$d=0.99$ 意味着随机跳转概率仅为 1%，冲浪者几乎总是在跟踪链接。这导致：

   • 链接结构的影响被放大——链接密集的页面群之间会”囤积”PageRank
   • 悬垂节点和链接农场（link farm）的效果被放大
   • 某些页面可能获得极高的 PR 值，另一些接近零

极端的例子：在 $d=1$（无随机跳转）时，如果 web 图不连通，PageRank 根本不唯一（每个连通分量有各自的平稳分布），幂迭代可能不收敛或收敛到非唯一解。

$d=0.85$ 是一个在”反映链接结构”和”计算可行性”之间的经验折中。在实际的搜索引擎评估中，这个值在 0.8-0.9 之间的变化对最终排序的影响并不剧烈（通常是 top-10 结果的微小调整），但对收敛速度的影响很大。

七、总结

PageRank 算法是机器学习史上少有的、同时具备”数学优雅性”和”商业成功性”的算法。它将互联网的链接结构建模为一个马尔可夫链，用平稳分布来度量网页的”重要性”，并将这一理论上极其简洁的模型扩展到了搜索、推荐、摘要等众多领域。

PageRank 给我们的最大启示是：复杂系统中的”重要性”，可以通过系统自身的结构（而非外部评判）来定义。这种”自指”的思想——重要性取决于”谁指向你”和”谁指向他们”——已经超越了网页排序，影响了从社交网络分析到科学文献评价的广泛领域。

在学习 PageRank 时，要理解的不只是实现细节，更是它如何将看似循环定义的问题（重要页面是被重要页面链接的页面）转化为一个良定义的数学问题（随机矩阵的平稳分布）。这种”用数学打通循环”的能力，是机器学习工程师的核心素养之一。

参考文献：

1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.
2. Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual web search engine. WWW7.
3. Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5), 604-632.
4. Mihalcea, R., & Tarau, P. (2004). TextRank: Bringing order into text. EMNLP.
5. Langville, A. N., & Meyer, C. D. (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings.