PageRank 算法

1998 年，斯坦福大学的两位博士生 Larry Page 和 Sergey Brin 在论文"The Anatomy of a Large-Scale Hypertextual Web Search Engine"中描述了一种给网页打分的方法，并用它建立了一个新的搜索引擎。他们把这个算法命名为"PageRank"——既是页面（Page）排名，也是 Larry Page 的姓。

这个算法被申请了专利（US Patent 6,285,999，"Method for node ranking in a linked database"，发明人 Lawrence Page，1998 年 1 月申请、2001 年 9 月授权）。值得注意的是：专利权人是斯坦福大学而非 Google——Page 当时是斯坦福研究生，专利归校方所有，Google 后来以长期独家许可换取（斯坦福因此获得约 180 万股 Google 股票）。它在相当程度上奠定了现代网络搜索的基础。

问题：网页的重要性如何排序？#

在 Google 之前，搜索引擎主要靠关键词匹配——页面中出现搜索词越多越靠前。这个策略被垃圾网站大量利用（关键词堆砌），搜索质量越来越差。

Page 和 Brin 的洞察：网页的重要性不只取决于内容，更取决于谁链接了它。一个被《纽约时报》链接的页面，应该比被垃圾网站链接的页面更重要。而《纽约时报》本身的重要性，又取决于谁链接了《纽约时报》……这是一个循环定义，需要迭代求解。

核心模型：随机冲浪者#

随机冲浪者模型（Random Surfer Model）是 PageRank 最直观的解释。想象一个随机上网的用户，他的行为如下： - 以概率 $d$（阻尼因子，damping factor，通常取 0.85）：随机点击当前页面的某个外链 - 以概率 $1 - d$（通常 0.15）：厌倦了，随机跳转到任意一个网页（"传送"）

$d = 0.85$ 意味着用户有 85% 的概率继续浏览、15% 的概率随机跳转。某个页面的 PageRank 就是：在这个随机过程的稳定分布（Stationary Distribution）下，用户停在该页面的概率。

数学定义#

设网络中有 $N$ 个页面，$PR(v)$ 是页面 $v$ 的 PageRank，$B_v$ 是所有指向 $v$ 的页面集合，$L(u)$ 是页面 $u$ 的出链数量：

$$PR(v) = \frac{1-d}{N} + d \sum_{u \in B_v} \frac{PR(u)}{L(u)}$$

两项各有含义：$\frac{1-d}{N}$ 是随机传送到任意页面的概率均摊；$\sum_{u \in B_v} \frac{PR(u)}{L(u)}$ 是从指向 $v$ 的所有页面中"流入"的 PR 值，每个页面把自己的 PR 平分给它的每一条出链。注意这是一个自引用方程组——每个页面的 PR 依赖其他页面的 PR，没有闭式解，只能迭代求解。

矩阵形式与幂迭代#

将 PageRank 写成矩阵形式。设转移矩阵 $M$，$M_{ij}$ 表示从页面 $j$ 到页面 $i$ 的转移概率（若 $j$ 有出链到 $i$，则 $M_{ij} = 1/L(j)$）。

加入传送项后，Google 矩阵（Google Matrix）：

$$G = d \cdot M + \frac{1-d}{N} \cdot \mathbf{1}\mathbf{1}^T$$

其中 $\mathbf{1}$ 是全 1 向量。PageRank 向量 $\vec{PR}$ 满足 $G \vec{PR} = \vec{PR}$——即 $\vec{PR}$ 是 $G$ 的特征值为 1 的特征向量（主特征向量）。

幂迭代法（Power Iteration）求解：

$$\vec{PR}^{(t+1)} = G \cdot \vec{PR}^{(t)}$$

从均匀分布 $\vec{PR}^{(0)} = [1/N, \ldots, 1/N]^T$ 出发，反复迭代直到收敛（相邻两次变化小于阈值 $\varepsilon$）。由 Perron-Frobenius 定理，迭代收敛速度由矩阵的第二大特征值 $|\lambda_2|$ 决定。对 Google 矩阵，$|\lambda_2| \leq d = 0.85$，收敛速度合理。早期 Google 报告约 50-100 次迭代收敛到百亿量级的网页规模。

为什么传送项保证唯一解#

值得追问一句：唯一解是碰巧成立，还是被设计出来的？答案是后者。

没有传送项时，$M$ 只是一个随机矩阵，稳定分布可能不唯一——若网页图分裂成几个互不连通的封闭区域，初始质量怎么分，最终各区域就留多少，方程有无穷多解。传送项 $\frac{1-d}{N}\mathbf{1}\mathbf{1}^T$ 的每个元素都是正数，它把 $G$ 变成正矩阵（所有元素严格大于零）：对正矩阵，Perron-Frobenius 定理保证主特征值 1 是单根，对应的正特征向量唯一。唯一性是被"给每个冲浪者留一条随时逃离的退路"这个设计决策买下来的。

同一个旋钮还控制了收敛速度：幂迭代每一步把误差向量在次主特征方向上的分量压缩到约 $d$ 倍，即每轮迭代误差大致乘以 0.85。几十轮就能把误差压到工程精度以下——这也解释了为什么收敛所需的轮数与网页总量几乎无关，这个算法天然能放大到互联网尺度。

特殊情形的处理#

悬挂节点（Dangling Nodes）：没有出链的页面（如 PDF 文档）。问题比"吸走 PR 值"更精确一些：转移矩阵 $M$ 的第 $j$ 列描述"从页面 $j$ 出发去哪"，悬挂节点对应一个全零列——列和为 0 而非 1，$M$ 不再是随机矩阵，PR 质量每轮迭代都从死胡同里漏掉一部分，长期趋于零。

标准修补：把悬挂节点视为"到站下车、随机传送"——即把每个全零列替换为各元素 $1/N$ 的均匀列，列和恢复为 1。工程上不必真的添加 $N$ 条虚拟边：每轮迭代先把所有悬挂节点的 PR 总量收集起来，均摊加到每个页面上即可，一轮只需 $O(N)$ 额外操作。

不连通分量（Spider Traps）：某些页面群形成只进不出的封闭子图，随机冲浪者一旦进入就出不去。阻尼因子 $d < 1$ 正是解决此问题——传送操作保证了遍历整个图的可能性，使 Google 矩阵是不可约（Irreducible）且非周期（Aperiodic）的，马尔可夫链收敛到唯一稳定分布。

PageRank 的理论基础：马尔可夫链#

PageRank 本质上是有限马尔可夫链（Markov Chain）的稳定分布问题。网页图对应马尔可夫链的状态转移图，稳定分布 $\pi$ 是转移矩阵的主特征向量。Perron-Frobenius 定理保证：对正随机矩阵（Google 矩阵满足此条件），稳定分布存在且唯一。

这将一个互联网规模的工程问题，根植于了 19 世纪的概率论数学。

个性化 PageRank：传送向量是一个旋钮#

标准 PageRank 的传送是均匀的——厌倦时等概率跳到任何页面。但公式里没有任何东西要求传送必须均匀。把均匀向量换成任意概率分布 $\vec{v}$（传送向量，teleport vector），方程变为：

$$\vec{PR} = (1-d)\,\vec{v} + d \cdot M \, \vec{PR}$$

解依然存在且唯一（$\vec{v}$ 仍保证正矩阵结构），只是"偏好"变了：离 $\vec{v}$ 中高权重页面近的页面，得分随之升高。这一个旋钮打开了两个方向。

主题敏感 PageRank（Topic-Sensitive PageRank）：Haveliwala（2002 年，WWW 会议）提出，预先对若干主题（取自开放目录 ODP 的分类）各算一个偏置向量——传送只跳到该主题的代表页面集合。查询到来时，按查询所属主题把各向量加权组合。代价是离线要为每个主题各跑一次幂迭代，换来的是 "jaguar" 在汽车主题下指向车、在动物主题下指向美洲豹。

随机游走重启（Random Walk with Restart）：把 $\vec{v}$ 集中在单个节点上，得到的向量度量"每个页面与该节点的亲疏"。这是推荐系统与图学习时代的标准工具——社交网络的"你可能认识的人"、图上的节点邻近度度量，本质都是单源个性化 PageRank。后文提到的 TrustRank 用的也是同一个旋钮，只是目的相反：把传送集中在人工审核过的可信种子页上，让"信任"随链接距离衰减，远离种子的页面天然得分更低，链接农场因此很难凭空制造权威。

PageRank 的局限与 SEO 军备竞赛#

PageRank 公布后，很快引发了搜索引擎优化（SEO，Search Engine Optimization）的军备竞赛：

• 链接农场（Link Farms）：建立互相链接的垃圾网站群，人为提升 PR 值
• 链接购买：付费让权威网站链接，虚增 PR
• 内容农场：大量生产低质但关键词密集的内容，吸引链接

Google 对此进行了大量改进： - TrustRank（Gyöngyi et al., 2004）：从可信种子网站出发，距离越远 PR 权重越低 - Spam Detection：检测异常链接模式 - Penguin/Panda 算法更新：针对特定垃圾 SEO 手段的惩罚机制

如今，Google 的排名算法融合了 200+ 信号，PageRank 只是其中之一，但仍是理解链接权威性的基础框架。

与 HITS 的对照：一个节点的两种身份#

几乎与 PageRank 同时，Kleinberg（1999）提出了另一条路线 HITS（Hyperlink-Induced Topic Search）。对比两者最能看清 PageRank 的设计取舍。

HITS 认为一个节点有两种身份：枢纽（Hub，善于指路，如目录页）与权威（Authority，内容本身好）。两个分数互相定义——好枢纽指向好权威，好权威被好枢纽指向——同样在邻接矩阵上幂迭代求解。这与 PageRank 的"重要性只有一种"形成对照。

更关键的区别在计算时机：HITS 是查询相关的——先按关键词取一个结果子集，在子图上算 hub/authority，每个查询都要在线迭代一次；PageRank 是查询无关的，离线算一次、在线查表。在互联网规模的低延迟要求下，这个差别几乎是决定性的：主流引擎采用了 PageRank 式的离线先验，HITS 则更多影响了后来的链接分析与社区发现研究。HITS 的另一弱点是对局部结构敏感：一个互相链接的小圈子就能在子图里刷出高 hub 分，操纵门槛比操纵全图低。

PageRank 的影响力延伸#

PageRank 思想远超搜索引擎，影响了多个领域。学术引用分析：科学论文的引用图上的 PageRank 给出比引用次数更准确的重要性排名（被重要论文引用比被普通论文引用更有价值）。

社交网络分析：Twitter 的"Who to Follow"推荐基于 PageRank 变种（SALSA 算法，Lempel & Moran 2001）。

生物信息学：蛋白质相互作用网络、基因调控网络的重要节点识别——"HubRank"类算法在生物网络中的应用正在增长。

随机游走在图上的普遍性：Google Random Walk、DeepWalk（2014）、Node2Vec（2016）等图神经网络前驱算法，都将 PageRank 的随机游走思想延伸为图的节点嵌入方法。

跨域连接#

• 随机过程：网页图上的随机游走是一条有限马尔可夫链，排名就是它的平稳分布。阻尼因子不是调参而是结构修补：它把转移矩阵改造成不可约且非周期的，唯一平稳分布才存在。收敛速度由第二大特征值决定，而该值被阻尼因子压住，所以迭代轮数与网页总量几乎无关——这是它能在互联网尺度上跑起来的全部原因。
• 社会网络分析：社会学早就用同一个方程定义声望——一个人的地位取决于认可他的人的地位，展开正是特征向量中心性。两者只差图的方向与边的语义，数学完全相同，因而共享同一个弱点：中心性只度量结构位置，说不出这个位置靠什么获得，所以它可以被结构操纵而实质不变。
• 机制设计：链接农场不是算法漏洞，是激励结构的可预测产物。这个指标不是激励相容的：被排名的人同时控制着排名所用的输入，公开度量等于公开操纵手册。这正是古德哈特定律的机制版本，也解释了对策为何必须换层次——可信种子、异常模式检测、把权重摊到两百多个信号上，都是在削弱单一输入的可操纵性。
• 计算语言学：只要能构造出"互相支持"的加权有向图，同一套幂迭代就给出排序。把句子当节点、句间相似度当边权，平稳分布就是抽取式摘要的句子权重；把词当节点、共现当边，得到的是关键词权重。适用范围由图的可构造性决定，与"网页"这个载体毫无关系。
• 信息检索与搜索：它是查询无关的先验，可以离线算一次、在线查表；相关性得分则必须逐查询计算。这条分工直接决定架构：能预计算的信号越多，在线延迟越低。也因此把它称作"排序算法"并不准确——它只提供一个与查询无关的权威度先验，须与匹配得分相乘才构成排序。

参考文献#

• Page, L., Brin, S. et al. "The PageRank Citation Ranking: Bringing Order to the Web." Stanford Technical Report, 1999.
• Brin, S. & Page, L. "The Anatomy of a Large-Scale Hypertextual Web Search Engine." WWW, 1998.
• Haveliwala, T. H. "Topic-Sensitive PageRank." Proceedings of the 11th International World Wide Web Conference (WWW), 2002.
• Kleinberg, J. "Authoritative Sources in a Hyperlinked Environment." Journal of the ACM 46(5), 1999.

延伸阅读#

• Langville, A.N. & Meyer, C.D. Google's PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, 2006.