PageRank 是一种链接分析算法,为有向网络中的节点赋予表示其重要性的数值分数。它最初用于对万维网上的网页进行排名,其中,一个网页指向另一个网页的超链接可视为对后者的关注或认可。其核心特点在于递归性:一个网页若得到重要网页的链接,就会获得较高分数,但每个提供链接的网页会将自身的贡献分配给它的各条出链。因此,仅凭入链数量并不能决定网页的排名。
PageRank 由拉里·佩奇和谢尔盖·布林于 20 世纪 90 年代在斯坦福大学开展研究期间开发,后来成为谷歌搜索的基础组成部分。从数学上看,它描述了一位理想化的网络浏览者在长期浏览过程中所处位置的概率分布:这位浏览者交替进行两种操作,即沿链接访问网页,以及按照指定的概率分布随机跳转到网页。这一表述将网页排名与概率论、网络分析和数值线性代数联系起来。
PageRank 既是一种衡量网页重要性的具体模型,也是一种分析网络的通用方法。其扩展形式可用于个性化排名、局部社群发现、推荐,以及引文网络和生物网络分析。不过,对其结果的解读仍取决于网络的构建方式:较高的 PageRank 分数衡量的是节点在某个特定连接体系中的显著程度,并不必然意味着准确、有用或优质。
起源与历史发展
随着万维网迅速扩张,单纯依靠文本进行搜索变得越来越困难,PageRank 正是在这一背景下诞生的。早期搜索系统能够将查询词与网页内容相匹配,但许多网页包含相似的词语,而且网页作者可以通过反复堆砌热门词语来吸引流量。超链接提供了另一种判断依据:它们记录了网页作者在各自独立维护的网站之间建立的关系。一个被许多其他网页链接的网页可能很有用,但不加区分地统计链接数量,无法辨别某个链接究竟来自重要的参考网站,还是来自鲜为人知或人为生成的网页。
PageRank 的思想渊源包括早期评估科学影响力的方法。1976 年,加布里埃尔·平斯基和弗朗西斯·纳林提出了一种衡量科学期刊影响力的递归方法,根据引用来源期刊的影响力为引用赋予权重。更一般地说,特征向量中心性根据节点邻居的重要性来确定该节点的重要性。PageRank 将这一类思想应用于有向、异质、不完整且规模极其庞大的万维网图。按出链数量进行归一化,以及处理不连通结构或使随机游走受困的结构,是它在实际应用中的关键特性。
佩奇和布林于 20 世纪 90 年代中期在斯坦福大学开展搜索研究,项目最初名为 BackRub。他们在 1998 年发表的论文《大型超文本网络搜索引擎剖析》中介绍了早期的 Google 搜索引擎,并说明了如何将 PageRank 与文本信息结合起来。1999 年,劳伦斯·佩奇、谢尔盖·布林、拉吉夫·莫特瓦尼和特里·威诺格拉德共同署名发表了更详尽的技术报告《PageRank 引用排名:为万维网建立秩序》。这一算法的名称既指网页,也呼应了佩奇的姓氏 Page。
PageRank 的历史意义并不在于它取代了所有其他检索方法。早期的 Google 架构将链接分析与锚文本、词语位置及其他信号结合使用。它的贡献在于,让一种通过递归计算、基本不依赖具体查询的网页重要性指标,能够在搜索引擎的规模上发挥作用。计算成本高昂的链接分析可以预先完成,而处理查询的系统只需将已存储的得分与每次搜索相关的信息结合起来。
2000 年推出的 Google 工具栏加入了 PageRank 指示器,此后这一术语在公众中获得了更广泛的含义。该指示器以 0 到 10 的等级显示粗略得分,并不揭示完整的内部排名过程。面向公众的工具栏得分于 2016 年停止提供。它的消失并不意味着底层概念已不再使用:Google 此后仍将 PageRank 列为其排名系统的组成部分,而现代搜索还融合了许多其他方法。因此,数学算法、历史上的工具栏指示器以及搜索结果的整体排序,是三个不同的对象。
网页图与链接的含义
PageRank 从一个有向图出发。每个节点代表一个对象,最初指的是网页;每条有向边代表一个对象到另一个对象的连接。从页面 指向页面 的超链接会形成一条边 。节点 的入邻居为它提供基于链接的支持,而节点 的出邻居则分摊 所能传递的支持。方向至关重要:获得一个重要页面的链接,与链接到该页面,并不是一回事。
对于无权图,设 表示节点 的出链数量。如果 ,最简单的模型会将该节点沿链接转移的概率按 的比例分配给每个目标节点。因此,一个得分为 、有三条出链的页面,在应用阻尼因子之前,会向每个目标页面贡献 。来自低分页面的十条入链,其贡献可能还不如来自高分页面的一条链接。反过来,即使一个页面很重要,如果它链接到数千个目标页面,那么它通过每条链接提供的贡献也很小。
这种解释要求先确定哪些对象算作节点、哪些连接算作边。网络爬虫会收集文档并提取超链接,但不同的统一资源定位符可能指向相同的内容。重定向、重复页面、不同的 URL 参数以及 URL 规范化处理,都会影响最终得到的图。图中的节点可以代表单个页面、整台主机或域名;这些选择会产生不同的排名问题。指向同一目标的重复链接是只计一次,还是赋予额外权重,同样取决于建模决策,而不是 PageRank 固有不变的属性。
有些页面在所收集的图中没有出链。这类节点称为悬挂节点。它们可能确实是没有后续链接的终端文档,也可能是未提取出超链接的文件,或是链接未能成功收集的页面。未经修正的随机游走无法从这样的节点选择下一条边。标准 PageRank 的处理方法是,让悬挂节点按照指定的分布重新分配其概率,通常采用与随机跳转相同的分布。这可以防止概率质量在计算过程中流失。
另一些图结构会带来不同的困难。一组页面可能只在内部相互链接,却没有任何路径返回图的其余部分。这类页面群通常称为排名汇聚区或蜘蛛陷阱。仅仅沿链接移动,最终可能使概率集中在这些封闭区域内。随机跳转提供了离开这些区域的途径,避免得分完全取决于偶然形成的连通结构。
此外,这个图只是网页网络的一个快照,而非网页网络本身。页面会变化,链接会消失,爬取也并不完整。因此,得分对应的是在特定时间收集到的一种特定表示。不应将其理解为人类访问次数的直接统计:随机浏览者是一个数学模型,而不是对实际浏览行为的测量。
随机浏览者模型与数学定义
标准的概率解释采用马尔可夫链。在每一步中,理想化的浏览者以概率 沿一条出链前往其他节点,以概率 进行随机跳转,其中 称为阻尼因子。随机跳转根据向量 选择目标节点,其中 ,且 。对于含有 个节点的图,均匀随机跳转设定 。历史上常用的取值是 ,但算法并不要求必须采用这个特定值。
采用列向量表示,定义列随机矩阵 ,其中 表示在沿链接移动的一步中,从节点 到达节点 的概率。对于无权图中的非悬挂节点,
每个悬挂节点对应的列都用一个概率向量替换;选择 ,便得到这里讨论的常用形式。PageRank 向量 满足
等价地,定义谷歌矩阵
则有 :PageRank 是浏览者转移过程的一个平稳分布。当 且 的所有分量均为正时,通过随机跳转可以到达每个节点,因此该链具有唯一的平稳分布,并且从任意初始概率向量出发都会收敛到这一分布。更一般地,只要 是随机矩阵且 ,对于任意概率向量 ,即使其部分分量为零,该不动点方程也有唯一解。
一个简单的例子可以同时说明重要性的递归传递和随机跳转。假设页面 链接到 和 ,而 仅链接到 , 仅链接到 。采用均匀随机跳转,并取 ,则有
解近似为 、 和 。虽然 只有一条入链,但这条入链来自得分最高的页面。页面 受益于两条入链,而 只能获得 沿链接传递的贡献的一半。
同一个方程也可以写成线性方程组:
或展开为
这一展开式表明,PageRank 是不同长度游走按几何权重形成的混合。较小的阻尼因子更侧重于短路径和随机跳转分布;较大的值则使更长的链接链条能够影响结果。在这一约定下,一次随机跳转之前连续沿链接移动的期望步数为 ,当 时约为 。
数值计算与大规模实现
计算 PageRank 的标准方法是幂迭代法。算法从概率向量 出发,通常取均匀分布,反复计算
每次迭代都将当前分数沿出边重新分配,并加入随机跳转的概率质量。计算时无须显式构造稠密的 Google 矩阵。该矩阵的随机跳转项结构简单,而超链接图通常是稀疏的:在所有可能的网页对中,只有很小一部分存在链接。
悬挂节点也可以在不显式构造稠密列的情况下处理。令 在非悬挂节点对应的列中存放归一化的出链权重,其余列均为零,并令 为悬挂节点的集合。当悬挂节点采用的替代分布为 时,更新公式为
因此,实现时只需要一次稀疏链接矩阵与向量的乘法、对悬挂节点分数求和,以及一次向量加法。如果图有 条边和 个节点,那么直接实现的一次迭代需要 的计算量;除去索引和具体表示方式带来的额外开销,图的存储空间与 成正比。
收敛性可由压缩性质得到。对于概率向量 和 ,有
若 ,则有如下后验误差界:
这一区分说明,相邻两次迭代结果的变化很小,并不等同于能够保证结果与精确解的距离很小。当 接近 1 时,最坏情况下的收敛界会变差。实际收敛速度可能更快,具体取决于图和初始向量。
在整个互联网的规模上,数据搬移往往与算术运算同样重要。在分布式计算中,各台机器分别存储图的不同分区,并将分数贡献发送给负责目标节点的机器。采用 MapReduce编程模型实现时,可以沿边输出分数贡献,再按目标节点进行聚合。反复同步、网络通信以及高度数节点的处理可能占据运行时间的大部分。因此,压缩、分区以及将频繁访问的图数据保留在内存中,可能比减少少量算术运算更为重要。
其他求解器则直接将 PageRank 视为稀疏线性方程组,采用克雷洛夫子空间迭代或外推等方法求解。动态方法在图更新后复用先前的解,而蒙特卡洛方法则通过抽样随机游走来估计分数。这些方法是否适用,取决于任务是需要计算全部分数、少量个性化分数,还是需要频繁更新。数值精度也很重要:即使向量误差很小,分数十分接近的节点也可能互换次序,因此,分数向量的收敛与排名靠前的节点列表的稳定,是相互关联但并不相同的要求。
在搜索引擎排序中的作用
PageRank 主要是一种与查询无关的信号。在给定的图结构和参数设置下,无论用户搜索的是天文学、铁路时刻表还是中世纪诗歌,一个页面都会有相应的得分。因此,这一得分可以离线计算,并与文档信息一同存储。相比之下,信息检索还必须判断文档是否切合某个特定查询。在整个网络中地位显著的页面,未必与某个专业问题相关;而相关性很高的新页面,最初可能很少得到链接的支持。
在搜索系统中,候选文档检索与最终排序是两个不同的环节。索引用于找出符合查询词或其他检索条件的文档,排序阶段则综合有关这些候选文档的各种证据。早期的 Google 设计将 PageRank 与文本匹配、锚文本以及查询词出现的位置等因素结合使用。现代系统可能会综合多类信号。因此,PageRank 并不是一套完整的搜索引擎设计方案,也不意味着搜索结果必须简单地按全局得分从高到低排列。
锚文本可以作为一个有益的对照。超链接中的文字可以描述其指向的页面,有时甚至比目标页面自身的描述更有信息量。PageRank 利用超链接的图结构,而基于锚文本的检索则利用其中的语言内容。这两种信号可以来自同一个链接,却回答不同的问题:前者关注目标页面的显著程度,后者关注页面的主题。因此,一个页面可能因指向它的描述性链接而受益,却不一定获得特别高的 PageRank 值。
这种概率得分也可以被视为在考虑查询之前,关于文档的先验证据。在这一解释下,查询匹配提供相关性证据,链接分析则提供背景性的偏好。这只是一种解释,并不要求每个搜索系统都采用显式的贝叶斯公式。实际组合时,可以使用人工设计的函数、统计排序模型或机器学习。不同信号的尺度差异很重要,因为概率、文本相关性得分和时效性特征并不是天然可比的量。
厘清以下几个区别,有助于避免常见误解。搜索结果的排列顺序,并不是原始 PageRank 值的公开展示。过去,工具栏上显示的高分并不保证页面在每个查询中都能排在前列。一个网站也并不存在一个数学上必然确定的 PageRank 值:原始模型针对页面进行排名,任何主机级或域名级的汇总都需要额外的聚合规则。一些第三方产品使用的“域名权威度”一词,也不是原始 PageRank 方程的另一个名称。
基于链接的排序,其运作时间尺度也不同于内容的即时发布。新文档可能在尚未积累大量链接时就已被索引,而旧页面即使内容已经过时,仍可能保持其在链接结构中的显著地位。因此,对于时效性强的查询和新近出现的话题,搜索系统还需要其他证据。PageRank 提供的是一种结构性证据;仅凭它本身,无法判定相关性、时效性、原创性或事实可靠性。
个性化、主题敏感及相关方法
PageRank 最简单的扩展是改变随机跳转的分布。个性化 PageRank 不再以均匀概率跳转到所有节点,而是将 集中在选定的网页、实体或用户兴趣上。对于单个种子节点 ,令 ,就会得到一个反复返回 的随机游走过程。由此得到的分数通过多条可能的有向路径衡量接近程度,并按路径长度进行衰减,而不只是统计共同邻居的数量或衡量最短路径。
主题敏感 PageRank 将这一思路应用于主题类别。塔赫尔·哈维利瓦拉在 2002 年的研究中计算了多个偏向不同主题的 PageRank 向量,并利用查询上下文将它们组合起来。这解决了单一全局排名的一项局限:在某个专业主题内的重要性,不一定与在整个万维网上的重要性一致。不过,仍应将主题敏感排名与对查询的完整语义理解区分开来。它改变的是随机游走的起始分布;概率如何传播,仍由链接及其归一化方式决定。
对于固定的转移矩阵 ,PageRank 关于 是线性的:
因此,如果 ,且各权重非负、总和为一,那么 。这使得预先计算好的向量可以组合使用。这里要求 保持不变,这一点很重要:如果每个悬挂列都用不断变化的个性化向量替换,转移矩阵也会随之改变,此时若不作进一步处理,就不能直接应用上述简单的线性关系。
加权 PageRank 用带权选择取代在出链之间的均匀选择。对于非负边权 ,非悬挂列可定义为
权重可以表示交互频率、关系强度,或人为设定的偏好。必须明确权重的含义:按点击次数为链接赋权,与平等对待所有超链接,得到的是不同的模型。“合理冲浪者”模型也同样考虑到,正文中醒目的链接可能比很少受到注意的页脚链接更容易被点击访问。
相关的递归排名方法在实质上各有不同。乔恩·克莱因伯格于 20 世纪 90 年代末提出的 HITS 算法,分别计算枢纽分数和权威分数。好的枢纽指向好的权威,而好的权威则被好的枢纽所指向。卡茨中心性对游走进行计数,并按长度施加衰减,但其本身并不采用 PageRank 中对出向概率的归一化方式。特征向量中心性也是一种关系密切的方法,不过,它在非连通图和有向图上的表现很大程度上取决于具体定义。
这些方法通常不能相互替代,否则所回答的问题也会改变。PageRank 对带重启机制的概率再分配进行建模;HITS 区分两种结构角色;其他中心性指标则可能衡量中介作用、可达性或单纯的连接数量。如何选择,取决于所要表达的含义究竟是声望、局部相关性、访问能力,还是中介作用。
网页搜索之外的应用
只要能够构建有实际意义的有向转移网络,就可以应用 PageRank。在引文分析中,节点可以代表论文、作者或期刊,边则可以代表引用关系。递归加权能够区分来自有影响力来源的引用与那些后续很少受到关注的来源所作的引用。Eigenfactor 等期刊层面的评价系统采用了类似的随机游走思路,但在聚合与归一化方式上各有选择。这类得分衡量的是引文网络的性质,并不能全面反映科学价值。
引文网络也凸显了时间的重要性。论文通常引用较早的研究,因此形成的图具有很强的时间方向性。沿引用关系进行不受限制的随机游走,会逐渐走向更早的文献;而全局得分可能仅仅因为已有研究有更多时间获得引用,就对其有所偏重。带有时间偏向的随机跳转、限定观测时间窗口以及按文献年龄进行归一化,都可以改变这种现象,但每种方法也都会改变所得指标的含义。跨领域比较得分同样需要谨慎,因为不同领域的引用密度和发表惯例各不相同。
在推荐系统中,个性化随机游走可以从某个用户、某件物品或一组先前选定的对象出发。图可以将用户与商品、商品与类别,或实体与描述性属性连接起来。在接近用户已知兴趣的位置重新开始游走,可以产生由多条路径支持的候选推荐。例如,在用户—物品二部图上,游走可以从某件物品移动到与其相关联的用户,再移动到其他物品。重启机制控制着推荐过程偏离初始偏好的程度。
自然语言处理应用使用根据文本关系构建的图。Rada Mihalcea 和 Paul Tarau 于 2004 年提出的 TextRank,将基于图的排序用于关键词提取和抽取式摘要等任务。候选词之间可以按共现关系连接,句子之间则可以按相似度连接。因此,排名靠前的句子,是在所选相似度度量下与其他句子具有紧密结构联系的句子。这种方法取决于预处理方式和边的定义;它并不能证明选出的句子在事实上正确,也不能保证其足以构成摘要。
生物学应用利用带重启的随机游走,将种子基因或蛋白质的相关性信息沿相互作用网络传播。这些方法可以对与实验确定的集合相关的节点进行优先级排序。其输出反映了相互作用数据、边的可靠性以及种子的选择。排名靠前的蛋白质只是与所建模网络相关的计算候选对象,并不自动构成其具有因果作用的证据。
个性化 PageRank 也可用于局部图聚类。从种子区域出发的概率质量可能持续集中在连接密集的邻域中,从而帮助识别社群,而无须穷尽处理所有可能的簇。近似算法可以利用这种局部性,只分配足够大的残余概率。这就将排序与数据挖掘联系起来:目标不再一定是为每个节点排序,而是发现指定起点周围在结构上紧密关联的邻域。
操纵、解释局限与评估
PageRank 在搜索中的应用,催生了人为制造其所衡量证据的动机。网络垃圾信息包括链接农场、付费链接,以及由受控网站组成的网络,旨在将排名影响力导向选定目标。由于 PageRank 具有递归性,一组相互配合的网页可以让概率在内部循环,并将其中一部分输送到外部。随机跳转机制确保了数学上定义明确的解,但无法区分独立赢得的认可与刻意安排的链接。
出链归一化能够限制操纵,却无法消除操纵。添加一条新的出边,通常只是将来源网页通过链接传递的贡献分配给更多目标,而不会产生额外的概率质量。然而,增加网页和链接可能改变平稳分布,尤其是当新增结构吸引了入链,或包含反复经过的路径时。其影响取决于整个网络,而不只是新建链接的数量。因此,总概率固定为一,并不意味着算法能够抵御恶意构造的图结构。
搜索引擎采用了超出原始方程范围的方法来应对这些问题,包括识别可疑的链接模式、对某些链接区别对待,以及使用独立的内容和行为信号。2005 年引入的 nofollow 链接关系,使网站运营者能够标明哪些链接不应被视为通常意义上的认可。后来,针对赞助链接和用户生成链接的进一步标记,又对链接所处的情境作了更细致的区分。这些标注会影响搜索系统对链接的解读;如何处理它们属于实现层面的策略,而不是 PageRank 抽象定义的一部分。
即使不存在操纵,网络中的显著地位也不等同于真实性或社会价值。与新成立或联系较少的信息来源相比,根基深厚的组织往往更容易积累链接。语言、地理位置、机构知名度,以及发布信息机会的不平等,都可能塑造图结构。递归排名可能延续这些结构性优势。这并不意味着分数在数学上有误,而是说,这些分数能否有效衡量“重要性”,取决于衡量目的以及边所代表的证据。
因此,评估不能止于证明收敛。数值测试考察残差、运行时间、内存使用量,以及对参数变化的敏感性。检索实验则通过测试集合,评估加入该分数能否改善针对具体查询的相关性。推荐实验考察能否发现有用的候选项,而科学网络研究可能会将排名与独立定义的结果进行比较。一个稳定且能高效计算的向量,仍可能不适合某个具体应用。
敏感性分析考察边、权重或随机跳转概率发生变化时,分数如何随之改变。一次扰动对向量整体的影响可能很小,却足以颠倒两个分数极为接近的节点的顺序。反过来,如果领先节点的分数差距较大,即使数值发生明显变化,其排序仍可能保持不变。当分数以排行榜的形式呈现时,这些区别十分重要:公布的名次可能暗示出比底层概率所能支持的更鲜明的差异,尤其是在图不完整、时间覆盖不均衡,或图的定义依赖于存在争议的建模选择时。