XML地图 深圳SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO培训 » 搜索引擎算法:PageRank算法

搜索引擎算法:PageRank算法

2018-10-11 | 人围观 | 关键词:


  PageRank算法
 

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

  [图片]图6-8 Google提出的PageRank算法
 

  6.3.1 从入链数量到PageRank
 

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

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

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

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

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

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

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

  6.3.2 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计算。
 

  [图片]图6-9 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得分。
 

  6.3.3 链接陷阱(Link Sink)与远程跳转(Teleporting)
 

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

  [图片]图6-10 链接陷阱
 

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

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

相关内容推荐:

Top