ITPub博客

首页 > Linux操作系统 > Linux操作系统 > PageRank 算法

PageRank 算法

原创 Linux操作系统 作者:broadviewbj 时间:2012-01-10 19:19:57 0 删除 编辑

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 个入链,分别来自于页面2356。每个链接传导的权值也如图上所标,那么页面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://space.itpub.net/13164110/viewspace-714497

 

1.jpg

2.jpg

3.jpg

这就是搜索引擎:核心技术详解.jpg

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/13164110/viewspace-714709/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2008-02-22

  • 博文量
    1031
  • 访问量
    1600879