pagerank · 网页排序

PageRank：网页图上的 power iteration

一张网页图上「哪一页更重要」没有天然的度量。入链数是最直白的答案，却把来自任何一页的推荐都算成同一份，结果刷分只需批量建站互指。PageRank 换了个提法：设想有人从任意一页出发不停点击链接，偶尔厌倦了就随手跳到另一页；长期来看他停在每一页上的时间比例，就是这一页的重要性。重要性不再由局部的入链数决定，而由整张图上一次 random walk 的极限行为决定。

本页把这个提法落成可算的东西：先给出 surfer 的转移规则，再看「一轮迭代等于一次向量乘矩阵」，然后处理两处会让极限不存在或不唯一的结构（出度为 0 的页面、只进不出的页面群），最后量一量收敛要多少轮。随机性在图上的另一种用法（边本身随机出现、性质在阈值处骤变）见随机图 · 概率方法与阈值现象。

1 · random surfer 模型

定义 1.1（random surfer） 在有 $n$ 个页面的有向图上，surfer 每一步二选一：以概率 $d$ 沿当前页面的出链等概率走一步；以概率 $1 - d$ 抛开链接结构，跳到全部 $n$ 页中等概率选出的一页。后一种动作叫 teleport。

记 $x_t(v)$ 为第 $t$ 步落在页面 $v$ 上的概率。PageRank 就定义为 $t \to \infty$ 时 $x_t$ 的极限 $\pi$ ，即这条 random walk 的 stationary distribution。这个定义有两点值得先说清楚。其一， $\pi$ 与起点无关，否则「重要性」会取决于 surfer 从哪一页开始，那就不是图的性质。其二， $\pi(v)$ 只在与全体页面比较时才有意义，绝对数值随 $n$ 缩放。§4 说明前一点为什么成立。

单条轨迹本身是随机的，但它的长期访问频率不是：走得越久，频率越贴近 $\pi$ 。这也给出 PageRank 的一种朴素算法——放一个 surfer 走上几百万步，数落脚次数。§2 的做法比它快得多，但两者算的是同一个量。

图 1-1 · 单条 random surfer 轨迹与它的访问频率。可拖动种子换一条轨迹，观察柱子如何逐渐贴上虚线标出的极限值。

2 · transition matrix 与 power iteration

把出链写成矩阵： $M_{uv} = 1 / \deg^{+}(u)$ 若 $u \to v$ ，否则为 0。每行之和为 1，这样的矩阵称作行随机的。补上 teleport，一步转移的完整矩阵是

G = d\,M + \frac{1 - d}{n}\,J

其中 $J$ 是全 1 矩阵。一轮迭代就是一次向量乘矩阵 $x_{t+1} = x_t\,G$ ，按分量展开即

x_{t+1}(v) = d \sum_{u \to v} \frac{x_t(u)}{\deg^{+}(u)} + \frac{1 - d}{n}

反复乘同一个矩阵、看向量收敛到哪里，这套做法叫 power iteration。它不解方程，也不求特征向量的显式表达；每轮只需按边求一遍和，代价 $O(m)$ ， $m$ 为边数。 $G$ 本身是稠密的（teleport 让每个元素都非零），但没有任何实现会把它存下来：上式右端只用到 $M$ 的稀疏结构与一个标量。

上式右端第二项与图结构无关，所以每一页的分数都不低于 $(1 - d)/n$ 。这条下界在实现里能逐位对上：§4 那张含陷阱的图里 D 没有任何入链，它的极限分数在 $d = 0.85$ 时精确等于 $0.15/6 = 0.0250$ 。

图 2-1 · power iteration 的逐轮分布。可切换图与 damping factor，观察柱子如何收敛到虚线，以及排名在第几轮定下来。

排名比分数稳得快，但也没有快到可以只跑三轮。强连通那张图上第 1 轮的排名是 C E A D B F，第 2 轮 D 一度窜到首位，终局却是 C A E D F B。前两名从第 3 轮起不再变，而 D 与 E 的相对次序一直互换到第 9 轮才定住——它们的极限分数分别是 0.17318 与 0.17433，只差 0.00115。分数接近的两页，需要的轮数比整体收敛更多。

3 · dangling node 与概率质量

出度为 0 的页面叫 dangling node（PDF、图片、抓取时未展开的页面都是）。它在 $M$ 里对应一整行零：质量进得去出不来。什么都不做的话， $x_t$ 的总和每轮减少 $d \cdot x_t(\text{dangling})$ ， $x_t$ 不再是概率分布。图 3-1 那张只有 F 缺出链的图， $d = 0.85$ 时总质量从 1 一路掉到 0.5329。

标准做法是把这一整行改写成均匀分布 $1/n$ ：surfer 走进死胡同就随手跳去任意一页。

注 · 不补 dangling node 得到的向量，归一化之后与补过的逐位相同。写本页时原以为「不补会毁掉排名」，实测推翻了这个预期：迭代式 $x \mapsto d\,xM + (1-d)/n$ 对末项是线性的，补 dangling node 只是把末项换成另一个常数，两个不动点因而严格成比例。core/pagerank.test.ts 对 $d = 0.5,\ 0.85,\ 0.99$ 与含一个、两个 dangling node 的图各验了一遍，归一化后的 L1 差都在 $10^{-16}$ 量级。这条依赖于「补法与 teleport 都取均匀分布」；personalized PageRank 里两者不同，结论随之失效。

图 3-1 · 不补 dangling node 时的质量泄漏。三列柱子依次是原始值、归一化值与补过的值，可拖动 damping factor 观察总质量下降而形状不变。

4 · damping factor 与极限的存在性

$d$ 通常取 0.85。它承担的不只是「厌倦概率」这个故事：teleport 项 $\frac{1-d}{n}J$ 把 $G$ 的每个元素抬到严格为正， $G$ 于是既 irreducible（任意两页互相可达，一次 teleport 就够）又 aperiodic（每页都有自环，周期为 1）。这两条正好是下面这条定理对矩阵的要求。

警示 · Perron–Frobenius 定理只断言存在与唯一，不给收敛速度。它说的是：对不可约的非负方阵，模最大的特征值是一个正实数且模严格大于其余特征值，与之对应的特征向量在相差一个正常数倍的意义下唯一、且分量全正。落到 PageRank 上就是 $\pi$ 存在、唯一、处处为正， $x_0$ 取哪个起点都不影响极限。至于要走多少轮才够接近，是另一个问题，见 §5。

去掉 damping（ $d = 1$ ）后两条前提同时失效。图 2-1 的第三张图里 E 与 F 互指、再无别的出链，构成一个 spider trap： $d = 1$ 时其余四页的分数全部趋于 0，而 E 与 F 的分数在奇偶轮之间来回换——第 400 轮是 $(0.4643,\ 0.5357)$ ，第 401 轮是 $(0.5357,\ 0.4643)$ ，power iteration 根本不收敛。这两页构成的闭合子链周期为 2，正是 aperiodic 失效的样子。把 $d$ 调回 0.85，序列立刻收敛（相邻两轮之差降到 $10^{-16}$ ），E 与 F 仍合占 0.7526，但另外四页都保住了 teleport 给的地板。

5 · 收敛速度与 second eigenvalue

这条上界在什么图上是紧的，实测给了答案。三张图各跑 60 轮，取第 10 到第 40 轮误差的几何平均比：强连通图 0.608，含 dangling node 的图 0.479，含 spider trap 的图 0.847。最后这个数几乎顶到 $d$ ，因为陷阱那两页构成的闭合子链周期为 2，让 $M$ 多出一个模为 1 的特征值 $-1$ ；前两张图则松了一大截。

$d$ 的角色也能量出来。把 $d$ 从 0.85 改到 0.95（收敛更慢，故改用第 20 到第 60 轮的窗口），强连通图上的速率从 0.615 升到 0.688，两者除以各自的 $d$ 都得 0.724。这个 0.724 与 $d$ 无关，是 $M$ 自身的 $|\lambda_2|$ ；damping 只是把它整体乘上 $d$ 。所以「 $d$ 越小收敛越快」是真的，代价是排名越来越被 teleport 项拉平。

关于 $\lambda_2$ 与图结构的关系，无向图上有更干净的说法（Laplacian 的 $\lambda_2$ 即 algebraic connectivity），见 random walk：从度数到 graph Laplacian §5。

6 · 参考文献

Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report, 1999-66.
Haveliwala, T. H., & Kamvar, S. D. (2003). The second eigenvalue of the Google matrix. Stanford University Technical Report, 2003-20.
Langville, A. N., & Meyer, C. D. (2004). Deeper inside PageRank. Internet Mathematics, 1(3), 335–380.
Bianchini, M., Gori, M., & Scarselli, F. (2005). Inside PageRank. ACM Transactions on Internet Technology, 5(1), 92–128.