Google 的 PageRank 算法 [1]

继续。以下文字翻译自http://pr.efactory.de/e-pagerank-algorithm.shtml。

--------------------------------------------------------------------------------



　　Lawrence Page和Sergey Brin在个别场合描述了PageRank最初的算法。这就是



PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) ——算法1

式中：



PR(A) :网页A页的PageRank值；

PR(Ti) :链接到A页的网页Ti的PageRank值；

C(Ti) :网页Ti的出站链接数量；

d :阻尼系数，0<d<1。

　　可见，首先，PageRank并不是将整个网站排等级，而是以单个页面计算的。其次，页面A的PageRank值取决于那些连接到A的页面的PageRank的递归值。



　　PR(Ti)值并不是均等影响页面PR(A)的。在PageRank的计算公式里，T对于A的影响还受T的出站链接数C(T)的影响。这就是说，T的出站链接越多，A受T的这个连接的影响就越少。



　　PR(A)是所有PR(Ti)之和。所以，对于A来说，每多增加一个入站链接都会增加PR(A)。



　　最后，所有PR(Ti)之和乘以一个阻尼系数d，它的值在0到1之间。因此，阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。



随机冲浪模型

　　Lawrence Page和Sergey Brin为以上这个PageRank算法给出了一个非常简单直观的解释。他们将PageRank视作一种模型，就是用户不关心网页内容而随机点击链接。



　　网页的PageRank值决定了随机访问到这个页面的概率。用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。



　　因此，一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。并且，阻尼系数d减低了这个概率。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。



　　阻尼系数d定义为用户不断随机点击链接的概率，所以，它取决于点击的次数，被设定为0-1之间。d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是(1-d)。(1-d)本身也就是页面本身所具有的PageRank值。