PAGERANK算法解析.ppt

《PAGERANK算法解析.ppt》由会员分享，可在线阅读，更多相关《PAGERANK算法解析.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、的矩阵被称为推移概率行列。nPageRank 的计算，就是求属于这个推移概率行列最大特性值的固有矢量。X=AXPageRank的计算(2)n采用递归的方法来求此特征值n递归结束标志：|Ranki+1-Ranki|将链接分块，并将块分发到多台机器上n2while(residual T)n所有机器同时计算，结果存入磁盘，并发送到中心服务器。n中心服务器收到所有机器发来的PageRank结果文件，将结果进行合并，并分发到所有机器上。nResidual=|Source Dest|nSource=Destn难点在于多台机器的并发控制参考文献n1 T.H.Haveliwala.Efficient computation of pagerank.Technical report,Stanford University,October 1999n2S.Brin and L.Page.The anatomy of a large-scale hypertextual web search engine.In Proc.of the Seventh World Wide Web Conference,1998.