PAGERANK算法解析

《PAGERANK算法解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、PageRank算法解析李永华2004.9.9OutlinePageRank的基本概念PageRank的计算PageRank计算算法的改进Google索引必须对每个网页的关键词建立索引倒排Term1－>Pi,Pj,…Term2－>Pk,Pl,…排序为每个网页赋予一个“PageRank”值查询匹配Q=Term1,Term2,…产生R=Pi,Pj,Pk,Pl…根据Pi,Pj,Pk,Pl…的“PageRank”值大小进行排序返回给用户PageRank的基本概念PageRank是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的回归关系，来判定所有网页的

2、重要性特点完全独立于查询，只依赖于网页链接结构可以离线计算每一张网页P有一个特定的Rank值r(P)r(P)的大小取决于三个因素：链入网页数链入网页的质量链入网页的链出网页数PageRank算法(1)定义将一个网页的所有链入网页的PageRank值除以该链入网页的链出网页数得到的结果进行累加，即得到该网页的PageRank值PageRank算法(2)PageRank的计算(1)网页链接关系建模－－矩阵网页i链接到网页j,则Aij=1,否则Aij=0;若网页个数为N，则此矩阵为N阶矩阵PageRank的矩阵是将此N阶矩阵A进行倒置，并把各个列矢量除以各自的

3、链接数。转换后的矩阵被称为[推移概率行列]。PageRank的计算，就是求属于这个推移概率行列最大特性值的固有矢量。X=AXPageRank的计算(2)采用递归的方法来求此特征值递归结束标志：

4、Ranki+1-Ranki

5、<阀值PageRank的计算(3)存在一些网页不链接任何网页，即此网页的出度（outdegree)为0，这种网页存为摇摆网页(danglingweb)。摇摆网页的存在将使得递归过程中Rank值会比实际值小。引入了一个新的矩阵PageRank的计算(3)PageRank的计算(4)需要两个数组Source和Dest分别保存上一次递归的结果

6、和本次递归的结果。经验表明，PageRank的值可用单精度浮点来表示；初值可以任意设置；c＝0.85PageRank计算算法的改进(1)假定网页的数量为N，则数组Source需要4Nbyte内存大小。当N=2.5亿(天网目前的网页数量），则需内存1G。如果N上升到10亿时，数组Source需要4G的内存，无法完全放在内存中。通过上面的算法可以看出，数组Source是顺序访问的，而数组Dest是随机访问的，如果不能够完全放在内存中，则需要通过文件进行内存映射，势必产生大量的I/O操作。PageRank计算算法的改进(2)分块的思想将网页链接矩阵进行分块，是

7、的每块Dest数组能够容纳在内存中。按块来分别计算PageRank值。分块示例PageRank计算算法的改进(3)PageRank计算算法的改进(4)PageRank计算算法的改进(5)多机并行计算PageRank由上面分块的思想，由于在一次迭代过程中，每块的计算是独立的，可以将这些计算分布到多台机器上并行计算。PageRank计算算法的改进(6)1>将链接分块，并将块分发到多台机器上2>while(residual>T){所有机器同时计算，结果存入磁盘，并发送到中心服务器。中心服务器收到所有机器发来的PageRank结果文件，将结果进行合并，并分发到所

8、有机器上。Residual=

9、

10、Source–Dest

11、

12、Source=Dest}难点在于多台机器的并发控制参考文献[1]T.H.Haveliwala.Efficientcomputationofpagerank.Technicalreport,StanfordUniversity,October1999[2]S.BrinandL.Page.Theanatomyofalarge-scalehypertextualwebsearchengine.InProc.oftheSeventhWorldWideWebConference,1998.