正文

PageRank——让谷歌腾飞的技术(4)

改变未来的九大算法 作者:(美)约翰·麦考密克


下图就是个例子。图中有A、B、C、D、E五个网页。如果从A开始,我们可以通过A访问B,然后又从B访问E,而从E我们又能点回A,也就是回到了出发点。这也意味着A、B和E三个网页组成了一个循环。

看来,在遇到循环时,目前“权重值”的定义(将超链接把戏和权重把戏结合起来)就碰到大麻烦了。看看在这个特例中会发生什么事情。网页C和D没有链入链接,因此其权重值为1。网页C和D都链向网页A,因此A的权重值是网页C和D权重值的和,也就是1+1=2。B网页从A获得的权重值为2,而E又从B获得权重值2。(这里谈到的情况都由上图左侧部分所体现。)但现在A的权重值要更新了:A从C和D各得到权重值1,但也从E得到权重值2,相加为4。于是B的权重值也需要更新:从A获得权重值4。然后E的权重值也要更新,它从B获得了权重值4。(现在谈到的情况都由上图右侧部分所体现。)依此类推:于是A的权重值变为6,B为6,E为6,于是A的权重值变为8……你懂了吧?随着循环进行,网页的权重值会一直增加。

这样计算权重值,会产生“鸡生蛋,还是蛋生鸡”的问题。如果我们知道A网页真正的权重值,我们就能计算B网页和E网页的权重值。而如果我们知道B网页和E网页真正的权重值,我们就能计算A网页的权重值。但由于这些网页彼此依赖,似乎这样计算根本行不通。

幸运的是,我们可以通过被称为随机访问者把戏(the random surfer trick)的技术解决这个“鸡生蛋,还是蛋生鸡”的问题。注意:对随机访问者把戏的初始描述,和到目前为止探讨的超链接及权重把戏没有任何关联。一旦了解了随机访问者把戏的基本原理,我们就会做一些分析,揭示其令人瞩目的品质:随机访问者把戏结合了超链接及权重把戏令人喜爱的属性,但在出现超链接循环时也行得通。

这个把戏从假想一个随机访问互联网的人开始。确切地说,访问者随机从万维网上的一个网页开始访问,然后检查该网页上的所有超链接,之后随机挑选出其中一个超链接进行点击。用户再检查打开的新网页,随机选择一个超链接打开。这个过程会持续进行,每一个网页都是通过随机选择前一个网页上的链接打开的。上图就是个例子。在这个例子中,我们假设整个万维网只有16个网页。框代表网页,箭头代表网页之间的超链接。其中标记了四个网页以便稍后进行参考。被访问者访问的网页用灰色表示,黑色箭头代表访问者点击的超链接,虚线箭头代表随机重新开始访问,这个在之后会讲到。


上一章目录下一章

Copyright © 读书网 www.dushu.com 2005-2020, All Rights Reserved.
鄂ICP备15019699号 鄂公网安备 42010302001612号