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 得分。
链接陷阱(LinkSink)与远程跳转(Teleporting)
互联网页面之间的链接结构实际上很复杂,上一小节介绍了PageRank 的计算过程,但是对于某些特殊的链接结构,按照上述方法计算PageRank 会导致问题,一个典型的例子就是“链接陷阱”(参见图6-10)。
图6-10 包含了3 个网页,相互有链接指向,形成了一个环形结构。这种结构类似于天体中的黑洞,在计算PageRank 的时候,该结构将导致系统只会吸收传入的分值,而不能将获得的分值传播出去,随着PageRank 一轮轮地连续运算,链接陷阱内的页面PageRank 得分越来越高,这与PageRank 的设计初衷相违背。
远程跳转是解决链接陷阱的通用方式,所谓的远程跳转,即在网页向外传递分值的时候,不限于向出链所指网页传递,也可以以一定的概率向任意其他网页跳转。对于链接陷阱内的网页来说,增加了远程跳转措施后,就像为每个页面增加了指向互联网任意其他页面的虚拟边,权值可以通过这种虚拟边向外传递,以此来避免链接陷阱导致的问题。
——本段文字节选自《这就是搜索引擎:核心技术详解》
图书详细信息:http://blog.csdn.net/broadview2006/article/details/7179396
分享到:
相关推荐
人工智能 PageRank算法的具体实现 有代码
无向图pagerank算法,java版本,完美运行!!!!!!!
很早就对Google的PageRank算法很感兴趣,但一直没有深究,只有个轮廓性的概念。前几天趁团队outing 的机会,在动车上看了一些相关的资料(PS:在动车上看看书真是一种享受),趁热打铁,将所看的东西 整理成此文。 ...
pageRank算法是机器学习中经典的算法,资源里面包含pageRank算法的原理分析,pageRank算法的源码,用的是python编写,适合初学者学习使用
南开大学大数据课程大作业一 :PageRank算法代码
数学模型部分课件 pagerank算法详解
pagerank算法 谷歌公司.ppt
用类封装了的pagerank算法模拟实现
近来自己在研究一下排序算法,结果在网上找了很久都只有两个Java实现的PageRank算法,其余的基本上是理论研究,对初学者帮助不大,希望能对你有些帮助。
Google的PageRank算法学习,超级经典
内含数据集。执行main.py即可
超大数据量的PageRank算法实现 ,北邮计算机应用编程实验源码
文档中讲述了如何在heritrix中使用pagerank的算法。根据文章中内容很容易将pagerank算法添加到heritrix中去
内含三个m函数,createRandomMetrics可以生成pagerank算法需要的矩阵,mypagerank计算pagerank值,runPageRank整合前两个函数。
搜索引擎PageRank算法研究
基于PageRank算法的搜索引擎优化策略.PDF 基于PageRank算法的搜索引擎优化策略.PDF 基于PageRank算法的搜索引擎优化策略.PDF
改进的非平均传递权值PageRank算法
Google搜索引擎的核心_PageRank算法综述 搜索引擎技术 系统资料 算法分析
搜索引擎PageRank算法实现及测试数据,测试输出,可执行文件。搜索引擎PageRank算法实现及测试数据,测试输出,可执行文件。
完整的用JAVA和MATLAB实现的Pagerank算法,且富有详细的注释