统计在线人数...

Google 的 PageRank 算法

[ 来源:蓝色理想 | 作者:戴云杰 | 时间:2003-12-23 下午 10:55:34 | 浏览:统计中... ]

rmined recursively by the PageRank of other documents. Since - even if marginal and via many links - the rank of any document influences the rank of any other, PageRank is, in the end, based on the linking structure of the whole web. Although this approach seems to be very broad and complex, Page and Brin were able to put it into practice by a relatively trivial algorithm.

  如此, 在PageRank概念中,文件的等级由与它连接那些文件的等级决定的。它们的等级再由与他们连接文件的等级决定。因此, 文件的PageRank由其他文件的PageRank总递归之和确定。因为,即使是在边缘的少量链接,任一个文件的等级都会影响些其他文件的等级,概言之,PageRank的等级是由整个网的连接结构决定的。虽然这种方法似乎是非常宽泛和复杂的, Page和Brin已经能够通过一个微不足道的运算法则将它投入实践了。

  个人总结:PageRank绝对是个很科学的小创意。说他科学,你会在我以后的文章中看到Google是如何将数学(具体来说多数是统计学)理论淋漓尽致地发挥在搜索技术之中。说他“小”,因为这些理论对于搞数学的人来说实在太微不足道了,甚至稍微有些科学高数知识的人都能理解。

  我一向认为,搜索引擎对于互联网的价值就好比桌面操作系统对于计算机的价值,微软已经无可争议地占领PC桌面之后,互联网的桌面之争从Internet诞生起就异常惨烈,后来Yahoo!因为进入互联网最早而取得阶段性胜利。不过那时候的搜索引擎对于我们来说好比是马桶……不得不用,一用就恶心。那时无论是Yahoo!AltaVistaAllTheWeb或者Lycos,搜索出来几乎都是大便。

  对于我来说,生命中出现搜索引擎的一天,是我同学的一个英国的同学告诉我用用看www.google.com

继续。以下文字翻译自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值。

  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忽略了互联网的网页总数,使得更易于计算。

上一页  [1] [2] 

共有0人参与评价,平均得分:0分
评论内容只代表网友观点,与本站立场无关! 查看完整内容
   

当前在线人数
QQ:748838 MSN:allen_xia#msn.com E-mail:allenxia666#126.com QQ群:站长联盟北方区-北京(28200145) 站长联盟南方区-上海(67713522)