课程汇报 · PageRank 算法深度解析

PageRank 要解决的问题很朴素：网页很多、链接更多，搜索引擎怎样判断哪个网页更重要？只数入链不够，因为一个不知名页面的推荐与一个权威页面的推荐，分量显然不同。PageRank 的核心因此是一个递归定义：重要页面指向的页面也更可能重要。

把互联网看成一张有向图

每个网页是一个节点，超链接是一条有方向的边。页面 $j$ 指向页面 $i$，可以理解为 $j$ 给 $i$ 投了一票；但 $j$ 如果同时指向很多页面，它的一票就要平均分摊。

图中：

• A 指向 B、C，因此把自己的权重各分一半；
• B 只指向 C，因此把全部权重给 C；
• C 只指向 A，因此把全部权重给 A。

如果 $L(j)$ 是页面 $j$ 的出链数，最直接的递推式是：

$$PR(i)=\sum_{j\to i}\frac{PR(j)}{L(j)}$$

这不是“先知道谁重要再计算”，而是从任意初始分数出发反复传播，直到分数基本不再变化。

随机冲浪者模型

上面的公式还有一个更直观的解释。想象一位用户正在随机浏览网页：每到一个页面，就等概率点击其中一条链接。长期运行后，用户停留在页面 $i$ 的概率就是它的 PageRank。

这个模型把排名问题变成了马尔可夫链的稳态分布问题。令 $M$ 为列随机转移矩阵，元素定义为：

$$M_{ij}=\begin{cases} \dfrac{1}{L(j)}, & j\to i,\\ 0, & \text{其他情况} \end{cases}$$

对上图按 A、B、C 排列，有：

$$M= \begin{bmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0 \end{bmatrix},\qquad \boldsymbol p^{(k+1)}=M\boldsymbol p^{(k)}$$

若从均匀分布 $\boldsymbol p^{(0)}=(1/3,1/3,1/3)^\top$ 开始，反复乘矩阵后会趋近：

$$\boldsymbol p=(0.4,0.2,0.4)^\top$$

A 与 C 并列最高，B 最低。原因并不只是入链数量：C 虽然接到 A、B 两条链接，但 A 的权重需要分成两份；A 只接到 C，却拿到了 C 的全部权重。

两个让朴素模型失效的问题

悬挂节点

如果某页面没有任何出链，随机冲浪者到达后就无路可走，对应转移矩阵的一整列为 0，概率质量会逐轮消失。常见处理是把悬挂节点视为等概率指向全部 $N$ 个页面，即把这一列替换为 $1/N$。

排名陷阱

如果若干页面只在内部互相链接、没有链接到外部，随机冲浪者一旦进入就永远出不来。这会让局部小团体吸走全部概率，也使结果依赖图结构是否不可约、是否存在周期。

阻尼 PageRank

PageRank 用“偶尔不点链接，随机跳到任意页面”同时解决上述问题。每一步：

• 以概率 $d$ 沿当前页面的链接前进；
• 以概率 $1-d$ 随机跳到任意页面。

经典取值是 $d=0.85$，但它是超参数，不是数学定律。公式变为：

$$\boldsymbol p^{(k+1)} =dM\boldsymbol p^{(k)} +\frac{1-d}{N}\boldsymbol 1$$

相应的逐页形式是：

$$PR(i)=\frac{1-d}{N} +d\sum_{j\to i}\frac{PR(j)}{L(j)}$$

对三页面示例使用 $d=0.85$，收敛后约为：

$$PR(A)=0.3878,\quad PR(B)=0.2148,\quad PR(C)=0.3974$$

随机跳转把少量分数均匀发给所有页面，所以 B 不会低到没有存在感，同时原有链接结构仍占主导。

幂迭代怎样计算

实际网页图巨大而稀疏，不会真的构造一个稠密的 $N\times N$ 矩阵。实现时只保存每个页面的出链，再按边传播分数：

1. 初始化每个页面的分数为 $1/N$；
2. 先给每个页面放入基础分数 $(1-d)/N$；
3. 将悬挂节点总分数的 $d$ 倍均匀分给全部页面；
4. 对每条边 $j\to i$，向 $i$ 加上 $d\,PR(j)/L(j)$；
5. 若新旧向量差异低于阈值则停止，否则继续。

常用停止条件是 $L_1$ 差异：

$$\left\|\boldsymbol p^{(k+1)}-\boldsymbol p^{(k)}\right\|_1<\varepsilon$$

一次迭代只需遍历全部节点和边，时间复杂度约为 $O(N+E)$，空间复杂度也可保持在 $O(N+E)$。

为什么会收敛

先把悬挂列替换为均匀分布，使 $M$ 成为列随机矩阵；加入随机跳转后，新的转移矩阵可写为：

$$G=dM+(1-d)\frac{1}{N}\boldsymbol 1\boldsymbol 1^\top$$

它的每个元素都为正。依据 Perron–Frobenius 定理，这样的随机矩阵存在唯一的最大特征值 $1$，对应唯一的正稳态向量；从任意概率分布开始做幂迭代，都能收敛到这个向量。随机跳转不只是一个工程补丁，它还给出了唯一性和收敛性的数学保证。

不只是网页排名

PageRank 的实质是“在有向关系图上传播重要性”，因此还可以迁移到：

• 引文网络：被重要论文引用的论文获得更高权重；
• 社交网络：被重要账户关注或转发的账户更重要；
• 推荐系统：在用户—物品或物品—物品图上传播偏好；
• 反垃圾与 TrustRank：从可信种子出发做个性化传播，削弱链接农场；
• 个性化 PageRank：把均匀跳转向量换成用户偏好的分布。

最后要记住，PageRank 衡量的是链接结构中的中心性，不等同于内容正确、质量高或适合某位用户。现代搜索排序会把它与文本相关性、质量、安全性和个性化等大量信号结合使用。

一页复习

• 图模型：网页是节点，链接是有向边；
• 分票规则：页面的权重按出链数平均分给目标页面；
• 概率解释：PageRank 是随机冲浪者的长期访问概率；
• 核心修正：以概率 $1-d$ 随机跳转，解决悬挂节点和排名陷阱；
• 计算方法：在稀疏图上做幂迭代，直至向量收敛；
• 数学本质：求 Google 矩阵特征值 $1$ 对应的稳态向量。