PageRank 算法

PageRank 算法

PageRank 是Google 创始人于1997 年构建早期的搜索系统原型时提出的链接分析算法（参见图6-8），自从Google 在商业上获得空前的成功后，该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在PageRank 算法基础上衍生出来的。

 

 

 

从入链数量到PageRank

在PageRank 提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入链越多，则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的效果。

PageRank 除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。

对于某个互联网网页A 来说，该网页PageRank 的计算基于以下两个基本假设：

· 数量假设：在Web 图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。

· 质量假设：指向页面A 的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A 越重要。

通过利用以上两个假设，PageRank 算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank 得分，直到得分稳定为止。

PageRank 计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用PageRank 来进行排序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回PageRank 值最高的页面。

PageRank 计算

本节探讨PageRank 的具体计算过程。PageRank 的计算充分利用了上节提到的两个假设：数量假设和质量假设。网页通过链接关系构建起Web 图，在初始阶段，每个页面设置相同的PageRank 值，通过若干轮的计算，会得到每个页面所获得的最终PageRank 值。随着每一轮的计算进行，网页当前的PageRank 值会不断得到更新。

在一轮更新页面 PageRank 得分的计算中，每个页面将其当前的PageRank 值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank 得分。当每个页面都获得了更新后的PageRank 值，就完成了一轮PageRank 计算。

下面以如图 6-9 所示的例子来说明PageRank 的具体计算过程。图中包含7 个页面，其页面编号分别从1 到7，页面之间的链接关系如图所示。这里要注意的一点是：如图6-9所示的情况已是经过若干轮计算之后的情形，每个页面已经获得了当前的PageRank 分值，比如页面1 当前的PageRank 分值为0.304，页面2 当前的PageRank 分值为0.166，其他页面的对应PageRank 数值也在图中标出。我们接下来看看从当前的状态出发，如何进行下一轮的PageRank 计算。

在 PageRank 计算中，从页面A 指向页面B 的某个链接的权值，代表了从页面A 传导

到页面B 的PageRank 分值。而对于页面A 来说，如果有多个出链，那么页面A 本身的PageRank 分值会均等地分配给每个链接。比如图6-9 中的页面4，其当前PageRank 分值为0.105，包含3 个出链，分别指向页面2 、页面3 和页面5，所以每个出链获得的分值为0.035。图 6-9 中其他链接的权值也与页面4 的出链一样，通过类似计算可以得到。

 

 

 

获得了每个链接传导的权值后，即可进行新一轮的PageRank 计算。要想得到各个页面节点的得分，只需将网页入链所传入的分值汇总即可。比如图6-9 中的页面1，有4 个入链，分别来自于页面2、3、5、6。每个链接传导的权值也如图上所标，那么页面1 的新的PageRank值为4 个入链传入的权值之和，即：

PR(1)=0.166+0.071+0.045+0.023=0.305

即得分从上一轮的0.304 更新到0.305。

其他页面节点也依次如此计算，以获得新的PageRank 分值，当所有页面节点的分值得到更新，就完成了一轮PageRank 计算。如果在新的一轮PageRank 计算之后，发现总体而言，页面节点的PageRank 值基本稳定，不再发生较大变化，即可结束PageRank 的计算，以此时得到的得分，作为最后排序时可以利用的PageRank 得分。

链接陷阱（Link Sink）与远程跳转（Teleporting）

互联网页面之间的链接结构实际上很复杂，上一小节介绍了PageRank 的计算过程，但是对于某些特殊的链接结构，按照上述方法计算PageRank 会导致问题，一个典型的例子就是“链接陷阱”（参见图6-10）。

 

 

 

图6-10 包含了3 个网页，相互有链接指向，形成了一个环形结构。这种结构类似于天体中的黑洞，在计算PageRank 的时候，该结构将导致系统只会吸收传入的分值，而不能将获得的分值传播出去，随着PageRank 一轮轮地连续运算，链接陷阱内的页面PageRank 得分越来越高，这与PageRank 的设计初衷相违背。

远程跳转是解决链接陷阱的通用方式，所谓的远程跳转，即在网页向外传递分值的时候，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转。对于链接陷阱内的网页来说，增加了远程跳转措施后，就像为每个页面增加了指向互联网任意其他页面的虚拟边，权值可以通过这种虚拟边向外传递，以此来避免链接陷阱导致的问题。

 

 

——本段文字节选自《这就是搜索引擎：核心技术详解》

图书详细信息:http://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=3054077