Google网页排序算法中PageRank值(3)

社会环境下网页重要性的研究

C(Ti) :网页Ti的出站链接数量； d :阻尼系数，0

上式最初算法只是表达了PageRank的基本计算原理，并不具有普遍性，因为没有迭代收敛的步骤。

所有PR(Ti)之和还要乘以一个阻尼系数d，它的值在0到1之间。阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。

一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。并且，阻尼系数d减低了这个概率。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。

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

图2.1

假设一个小网站由三个页面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.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(B)=15/13 = 1.15384615

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

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

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

1 1 1.0625

1 0.75 0.765625

1 1.125 1.1484375

11

社会环境下网页重要性的研究

3 4 5 6 7 8 9 10 11 12

1.07421875 0.76855469 1.15283203 1.07641602 0.76910400 1.15365601 1.07682800 0.76920700 1.15381050 1.07690525 0.76922631 1.15383947 1.07691973 0.76922993 1.15384490 1.07692245 0.76923061 1.15384592 1.07692296 0.76923074 1.15384611 1.07692305 0.76923076 1.15384615 1.07692307 0.76923077 1.15384615 1.07692308 0.76923077 1.15384615

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

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

2.2.2 传统 PageRank算法向量表达形式

2的计算,首先每个网页文档的PageRank 值可上述过程在本质上可以表达为特征向量○

以表示一个向量 ,即一个 N 行1列的向量 (N 为所有的网文档数)，为了便于计算，开始时可以给每个元素的值设为 1/ N。

Rank = ［1/ N ］n ×1

设M为一个随机矩阵，它的横纵行列数分别为整个网页集合的文档数，每个矩阵元素值表示两两网页之间的链接关系,即如果网页Di指向Dj，则矩阵元素Mij 对应的值为1/ Ni ( Ni表示Di的链出网页数)；如果网页Di不指向Dj，则M ij值为 0。

?m11,m12,..........,m1n???m21,m22,.........,m2n??? M=?..................................???mn1,mn2,..........mnn?所以 , PageRank 值的计算就可以表示为：

Rank = MT ×Rank (2.3)

而且这个过程是个反复迭代的过程,直至 Rank值最终收敛。但是，实际的网页结构并

12

社会环境下网页重要性的研究

非表现为一个完全牢固的链接图，不是所有的网页都可以从其他网页 通过超链来达到，而PageRank值的计算正依赖于此，所以Page等人就提出了改进方案，对存在的等级沉没(Rank Sink)和等级泄漏(Rank Leak)[8]等问题进行了有效的解决。整个网页图中的一组紧密链接的网页如果没有外出的链接就产生等级沉没，一个独立的网页如果没有外出的链接就产生等级泄漏。所以，Page改进措施为：一是剔除产生等级泄漏的独立网页以消除其不利影响；二是给产生等级沉没的网页添加一个指向链入网页的返回链接，此时使得所有网页 PageRank 值的计算就不完全依赖现有链接了，所以修正的PageRank计算公式为 ：

R?u??C?v?B(u)R(v)/N(v)?CE(u) (2.4)

其中，‖R′‖1=1，对应的矩阵形式为V’=c(AV’+E)。

E(u)是个常量，它可以抑制 PageRank 值的传播，使得所有网页的PageRank 值至少会为E ( u) ，而不会为0。具体的E ( u)值可以有多种取法，简单的做法可以设为p，如取1/ N ( N为网页文档总数)。

从特征向量的角度来考察，可以设置P列向量以代表每个网页文档都有的、相同的E ( u)

P??1/N?n?1

PageRank迭代运算都利用了特征向量作为理论基础和收敛性依据[9]，这是超链接环境下此类算法的一个共同特征。

设置 D 向量以代表网页文档的链出网页数是否为 0 , 即 1 如果网页Di的链出网页数为0 Di= 0 如果网页Di的链出网页数非0

则上述 PageRank 的计算可以进一步表达为 :

Rank = C ( M + P ×D T ) ×Rank + C P

2.3 传统Google PageRank的缺陷和改进方法

基于链接分析的算法 ,目前的研究都还很不成熟，无论是Page Rank算法，还是HITS算法等，有一些共同的问题影响着算法的精度。

( 1) 根集的质量。根集质量应该是很高的 , 否则 , 扩展后的网页集会增加很多无关的网页 , 产生主题漂移、主题泛化等一系列的问题 ,计算量也增加很多。 算法再好 ,也无法在低质量网页集找出很多高质量的 网页。

(2) 锚文本的利用。锚文本有很高的精度 ,对链接 和目标网页的描述比较精确。上述算法在具体的 实现中利用了锚文本来改进算法。如何准确充分地利用锚文本 ,对算法的精度影响很大。

13

社会环境下网页重要性的研究

(3) 噪音链接。Web 上不是每个链接都包含了有用的信息，比如广告、站点导航、赞助商、用于友情交换的链接，对于链接分析不仅没有帮助，而且还影 响结果。如何有效去除这些无关链接，也是算法的一个关键点。

(4) 查询的分类。每种算法都有自身的适用情况 , 对于不同的查询 ,应该采用不同的算法 ,以求获得最好的结果。因此 ,对于查询的分类也显得非常重要。

文中对Google PageRank算法进行了深入探讨和比较,但在这几个方面需要继续做深入的研究,相信在不久的将来会有更多的有价值的成果出现。本文正是针对Google PageRank存在的问题进行算法的改进，将改进的算法和Google PageRank的传统算法完美结合，不仅解决的Google PageRank完全不考虑访问者自身知识水平的缺陷，还预示了将不同算法结合是未来搜索引擎的发展趋势。

14

社会环境下网页重要性的研究

3．Google PageRank 算法改进

3.1由访问者知识水平及其投票的情况决定网页排名的 PageRank 算法

3.1.1 算法中PR值的含义

在Google PageRank传统算法中，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，Google才更改了度量。 转化为0~10度量 。因此可以认为传统算法的网页PR值，反映了网页的热度(访问人数)，PR值越大，则表示网页越热，越多人访问。

在改进算法中，访问者的PR值表示为PRin，PRin越大则表示访问者的专业知识水平越高。网页的PR值表示为Pij，Pij越大表示网页的权威性、正确性越大。

3.1.2 从投票角度分析算法的本质

从投票的角度来分析两种算法的本质：Google PageRank传统算法中，从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票，由其他网页对网页本身的投票来计算网页的PR值。在改进算法中，访问者对网页的投票的被认同度就是其他访问者对他的投票，由其他访问者对他的投票来计算访问者的PR值。在计算网页PR值时，网页由访问者对它的投票来决定网页的PR值。

不是每个访问者和网页的投票都是对访问者或者网页的PR值贡献一样的，因为每个访问者和网页的权重不一样，两者的权重分别与它们的知识水平和网页权威性有关。因此计算两者PR值之前要计算两者的权重。

权重是一个相对的概念，是针对某一指标而言。某一指标的权重是指该指标在整体评价中的相对重要程度。

权重表示在评价过程中，是被评价对象的不同侧面的重要程度的定量分配，对各评价因子在总体评价中的作用进行区别对待。事实上，没有重点的评价就不算是客观的评价。

打个比方说, 一件事情, 你给它打100分, 你的老板给它打60分, 如果平均, 则是(100+60)/2=80分. 但因为老板说的话分量比你重, 假如老板的权重是2, 你是1, 这时求平均值就是加权平均了, 结果是(100*1 + 60*2)/(1+2)=73.3分, 显然向你的老板那里倾斜了。假如老板权重是3，你的权重是1，结果是(100*1+60*3)/(1+3)=70。这就是根据权重的不同进行的平均数的计算，所以又叫加权平均数。

同样道理每个访问者和每个网页的权重都是不同的因为他们的权威性是不同的。例如：一个工程院院士关于PageRank网页的投票的权重，比我对PageRank网页的投票的权重大

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库Google网页排序算法中PageRank值(3)在线全文阅读。