Google 的 PageRank 算法

作者:佚名       来源于:中国营销策划网

式中:

  • PR(A) :网页A页的PageRank值;
  • PR(Ti) :链接到A页的网页Ti的PageRank值;
  • C(Ti) :网页Ti的出站链接数量;
  • d :阻尼系数,0

  可见,首先,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值。

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

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

  这里的N是整个互联网网页的总数。这个算法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忽略了互联网的网页总数,使得更易于计算。

 

作者:戴云杰

|<< << < 1 2 3 > >> >>|


 3/3   首页 上一页 1 2 3

上一篇开拓思路 基于链接的两个研究

下一篇Overture注册方式简介

 【相关文章




版权声明:文章观点仅代表作者观点,作为参考,不代表本站观点。部分文章来源于网络,如果网站中图片和文字侵犯了您的版权,请联系我们及时删除处理!转载本站内容,请注明转载网址、作者和出处,避免无谓的侵权纠纷。