《PageRank算法解析.ppt》由会员分享，可在线阅读，更多相关《PageRank算法解析.ppt（18页珍藏版）》请在三一办公上搜索。
1、PageRank算法解析,李永华,Outline,PageRank 的基本概念PageRank的计算PageRank计算算法的改进,Google,索引必须对每个网页的关键词建立索引倒排Term1Pi,Pj,Term2Pk,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进行倒置，并把各个列矢量除以各自的链接数。转换后的矩阵被称为推移概率行列。PageRank 的计算，就是求属于这个推移概率行列
3、最大特性值的固有矢量。X=AX,PageRank的计算(2),采用递归的方法来求此特征值递归结束标志：|Ranki+1-Ranki|阀值,PageRank的计算(3),存在一些网页不链接任何网页，即此网页的出度（outdegree)为0，这种网页存为摇摆网页(dangling web)。摇摆网页的存在将使得递归过程中Rank值会比实际值小。引入了一个新的矩阵,PageRank的计算(3),PageRank的计算(4),需要两个数组Source和Dest分别保存上一次递归的结果和本次递归的结果。经验表明，PageRank的值可用单精度浮点来表示；初值可以任意设置；c 0.85,PageRank计
4、算算法的改进(1),假定网页的数量为N，则数组Source需要4N byte内存大小。当N=2.5亿(天网目前的网页数量），则需内存1G。如果N上升到10亿时，数组Source需要4G的内存，无法完全放在内存中。通过上面的算法可以看出，数组Source是顺序访问的，而数组Dest是随机访问的，如果不能够完全放在内存中，则需要通过文件进行内存映射，势必产生大量的I/O操作。,PageRank计算算法的改进(2),分块的思想将网页链接矩阵进行分块，是的每块Dest数组能够容纳在内存中。按块来分别计算PageRank值。分块示例,PageRank计算算法的改进(3),PageRank计算算法的改进(
5、4),PageRank计算算法的改进(5),多机并行计算PageRank由上面分块的思想，由于在一次迭代过程中，每块的计算是独立的，可以将这些计算分布到多台机器上并行计算。,PageRank计算算法的改进(6),1将链接分块，并将块分发到多台机器上2while(residual T)所有机器同时计算，结果存入磁盘，并发送到中心服务器。中心服务器收到所有机器发来的PageRank结果文件，将结果进行合并，并分发到所有机器上。Residual=|Source Dest|Source=Dest难点在于多台机器的并发控制,参考文献,1 T.H.Haveliwala.Efficient computation of pagerank.Technical report,Stanford University,October 19992S.Brin and L.Page.The anatomy of a large-scale hypertextual web search engine.In Proc.of the Seventh World Wide Web Conference,1998.,
