Google的PageRank算法学习.doc

文档介绍：Google的PageRank
1、入链对计算页面级别的影响
入链总是能增加当前页面的级别,尤其当前页与其下级页面构成回路时,这种贡献更大。如右图例,设ABCD各页初始级别为1,,PR(X)/C(X)=10。则易算出
PR(A) = 19/3 =
PR(B) = 11/3 =
PR(C) = 7/3 =
PR(D) = 5/3 =
如果A不在回路上,*10=5的收益。
阻尼系数越大,页面级别的收益越大,且整个回路上都能收到更大的收益(即入链收益更能平均地分布到各个回路页面上。针对上例,,则有
PR(A) = 419/35 =
PR(B) = 323/35 =
PR(C) = 251/35 =
PR(D) = 197/35 =
除回路上各个页面的级别值明显增大外,PR(A)/PR(D)的值敢明显减少了。
入链对整个回路上所有页面的级别值的增加之和,可以由下面这个公式得出.
(d / (1-d)) × (PR(X) / C(X))
这个公式,可以由简单推导出。
2、出链对计算页面级别的影响
增加出链不会影响整个web的总级别,但一个站点失去的级别值等于链到的站点的增加值之和。对于两个封闭的站点,从一个站点链上另一个站点时,增加的和减少的都是(d(/(1-d) × (PR(X) / C(X)).如果这两个站点互相链接,则此值减少。用随机冲浪模型可以解释这种现象,就是出链的增加,减少了用户访问站内页面的概率。举例如图,,则
PR(A) = + PR(B)
PR(B) = + PR(A)
PR(C) = + PR(D) + PR(A)
PR(D) = + 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将这样的链接称为悬摆链,它链到页面没有出链。悬摆链对页面的级别计算产生负面影响。如例,.
PR(A) = + PR(B)
PR(B) = + PR(A)
PR(C) = + 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在索引页面时,悬摆链的量很大,。为消除这种负面影响,google在计算级别时,将此类链接从数据库里去掉,在计算完毕后,再单独计算悬摆链所链到页面。由此可见,PDF类的文件还是可以放心地在网上发布的。
3、页面数量的影响
先看例子。,PR(X)