Google的PageRank算法学习

Google 的PageRank 1、入链对计算页面级别的影响 入链总是能增加当前页面的级别，尤其当前页与其下级页面构成回路时，这种贡献更大。如右图例，设 ABCD 各页初始级别为 1，阻尼系数为 0.5，PR(X)/C(X)＝10。则易算出 PR(A) = 19/3 = 6.33 PR(B) = 11/3 = 3.67 PR(C) = 7/3 = 2.33 PR(D) = 5/3 = 1.67 如果 A 不在回路上，则只能得 0.5*10=5 的收益。 阻尼系数越大，页面级别的收益越大，且整个回路上都能收到更大的收益（即入链收益更能平均地分布到各个回路页面上。针对上例，将阻尼系数改为 0.75，则有 PR(A) = 419/35 = 11.97 PR(B) = 323/35 = 9.23 PR(C) = 251/35 = 7.17 PR(D) = 197/35 = 5.63 除回路上各个页面的级别值明显增大外，PR(A)/PR(D)的值敢明显减少了。 入链对整个回路上所有页面的级别值的增加之和，可以由下面这个公式得出. (d / (1-d)) × (PR(X) / C(X)) 这个公式，可以由简单推导出。 2、出链对计算页面级别的影响 增加出链不会影响整个 web 的总级别，但一个站点失去的级别值等于链到的站点的增加值之和。对于两个封闭的站点，从一个站点链上另一个站点时，增加的和减少的都是(d(/(1-d) × (PR(X) / C(X)).如果这两个站点互相链接，则此值减少。用随机冲浪模型可以解释这种现象，就是出链的增加，减少了用户访问站内页面的概率。举例如图，设阻尼系数为 0.75，则 PR(A) = 0.25 + 0.75 PR(B) PR(B) = 0.25 + 0.375 PR(A) PR(C) = 0.25 + 0.75 PR(D) + 0.375 PR(A) PR(D) = 0.25 + 0.75 PR(C) 得： PR(A) = 14/23 PR(B) = 11/23 PR(C) = 35/23 PR(D) = 32/23 PR(A)+PR(B)=25/23 PR(C)+PR(D)=67/23 PR(A)+PR(B)+PR(C)+PR(D)=92/23=4 Page 和Brin 将这样的链接称为悬摆链，它链到页面没有出链。悬摆链对页面的级别计算产生负面影响。如例，阻尼系数为0.75. PR(A) = 0.25 + 0.75 PR(B) PR(B) = 0.25 + 0.375 PR(A) PR(C) = 0.25 + 0.375 PR(A) 得： PR(A) = 14/23 PR(B) = 11/23 PR(C) = 11/23 PR(A)+PR(B)+PR(C)=36/23<3 据Page 和Brin，Google 在索引页面时，悬摆链的量很大，主要是由于限制robot.tx t 的限制及索引了一些没有链出的文件类型如PDF 等。为消除这种负面影响，google 在计算级别时，将此类链接从数据库里去掉，在计算完毕后，再单独计算悬摆链所...