Kros Dai’ Blog No excuse, no panic

Google的PageRank算法(二)

  Lawrence Page和Sergey Brin在不同的刊物中发表了2个不同版本的PageRank的算法公式。在第二个版本的算法里,页面A的PageRank值是这样得到的:

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

  这里的是整个互联网网页的总数。这个算法2,并不是完全不同于算法1。随机冲浪模型中,算法2中页面的PageRank值就是在点击许多链接后到达这个页面页面的实际概率。因此,互联网上所有网页的PageRank值形成一个概率分布,所有RageRank值之和为1。



  相反地,第一种算法中随机访问到一个页面的概率受到互联网网页总数的影响。因此,算法2解得的PageRank值就是用户开始访问过程后,该页面被随机访问到的概率的期望值。如果互联网有100个网页,其中一个页面PageRank值为2;那么,如果他将访问互联网的过程重新开始100次(xdanger注:这句话具体含义是,该用户随机点击网页上的链接进入另一个页面,每点击一次都有一定概率因疲劳或厌倦或其他任何原因停止继续点击,这就是阻尼系数d的含义;每当停止点击后,即算作此次访问结束,然后随机给出一个页面让他开始另一次访问过程;让他将这样的“手续”重复进行100次),平均就有2次访问到该页面。

  就像前面所提到的,两种算法并非彼此是本质的不同。用算法2解得的PR(A)乘以互联网的总网页数N,即得到由算法1解得的PR(A)。Page和Brin在他们最著名的刊物《The Anatomy of a Large-Scale Hypertextual Web Search Engine》中调和了两种算法,文中声称算法1是将PageRank形成对于互联网网页的一个概率分布,其和为1。

   接下来,我们将使用算法1。理由是算法1忽略了互联网的网页总数,使得更易于计算。

<< Google的PageRank算法(一) | Google的PageRank算法(三) >>

This site is licensed under a Creative Commons License .