skip to content

PageRank 特性

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

三页面网站模型

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

PR(A)=0.5+0.5PR(C)PR(B)=0.5+0.5(PR(A)/2)PR(C)=0.5+0.5(PR(A)/2+PR(B))PR(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.07692308PR(B)=10/13=0.76923077PR(C)=15/13=1.15384615PR(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)
0111
110.751.125
21.06250.7656251.1484375
31.074218750.768554691.15283203
41.076416020.769104001.15365601
51.076828000.769207001.15381050
61.076905250.769226311.15383947
71.076919730.769229931.15384490
81.076922450.769230611.15384592
91.076922960.769230741.15384611
101.076923050.769230761.15384615
111.076923070.769230771.15384615
121.076923080.769230771.15384615

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

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

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