Kros Dai’ Blog No excuse, no panic

Google的PageRank算法(三)

PageRank特性

  PageRank的特性可以通过以下范例用插图表示。 

  假设一个小网站由三个页面A、B、C组成,A连接到B和C,B连接到C,C连接到A。虽然Page和Brin实际上将阻尼系数d设为0.85,但这里我们为了简便计算就将其设为0.5。尽管阻尼系数d的精确值无疑是影响到PageRank值的,可是它并不影响PageRank计算的原理。因此,我们得到以下计算PageRank值的方程:

(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

  这些方程很容易求解,以下得到每个页面的PageRank值:



PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615

  很明显所有页面PageRank之和为3,等于网页的总数。就像以上所提的,此结果对于这个简单的范例来说并不特殊。

  对于这个只有三个页面的简单范例来说,通过方程组很容易求得PageRank值。但实际上,互联网包含数以亿计的文档,是不可能解方程组的。

PageRank的迭代计算

  由于实际的互联网网页数量,Google搜索引擎使用了一个近似的、迭代的计算方法计算PageRank值。就是说先给每个网页一个初始值,然后利用上面的公式,循环进行有限次运算得到近似的PageRank值。我们再次使用“三页面”的范例来说明迭代计算,这里设每个页面的初始值为1。

迭代次数 PR(A) PR(B) PR(C)
0 1 1 1
1 1 0.75 1.125
2 1.0625 0.765625 1.1484375
3 1.07421875 0.76855469 1.15283203
4 1.07641602 0.76910400 1.15365601
5 1.07682800 0.76920700 1.15381050
6 1.07690525 0.76922631 1.15383947
7 1.07691973 0.76922993 1.15384490
8 1.07692245 0.76923061 1.15384592
9 1.07692296 0.76923074 1.15384611
10 1.07692305 0.76923076 1.15384615
11 1.07692307 0.76923077 1.15384615
12 1.07692308 0.76923077 1.15384615

   重复几次后,我们的到一个良好的接近PageRank理想值的近似值。根据Lawrence Page和Sergey Brin共开发表的文章,他们实际需要进行100次迭代才能得到整个互联网的满意的网页级别值。

  同样,用迭代计算的方式,每个网页的PageRank值之和仍然收敛于整个网络的页面数的。因此,每个页面的平均的PageRank值为1。实际上的值在(1-d)(dN+(1-d))之间,这里的N是互联网网页总数。如果所有页面都连接到一个页面,并且此页单独地连接自身,那么将出现理论上的最大值。

 << Google的PageRank算法(二) | PageRank在Google搜索中的实现 >>

This site is licensed under a Creative Commons License .