第五章 5.1 网页等级算法全面阐释 Analysis of PageRank Algorithm

互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数，并用页面长度和html标签的重要性提示等进行权重修订。链接流行度技术通过其它文档链接到当前页面链入数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。PageRank计算页面的重要性，对每个链入赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。一个网页的重要性是一种内在的主观事情,这取决于读者兴趣,知识和态度. 但仍有许多可说是客观的相对重要性的网页. 简单地介绍如何给网页评级,有效衡量人们对网页的兴趣和重视程度。

PageRank的数学定义:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中：PR(A):页面A的网页级别,
PR(Ti)：页面Ti的网页级别，页面Ti链向页面A，
C(Ti)：页面Ti链出的链接数量，
d：阻尼系数，取值在0.85－0.95之间，一般取值为0.85，此因素直接影响迭代计算PageRank过程中的收敛速度

由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值 是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A 的排序贡献。

公式的来历：Google公司的创始人Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上 链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼 系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的 网页级别。PageRank的计算是封闭流通模型，所有页面的网页级别之和等于网页初始级别的和。

容易从PageRank的数学定义得出一个恒等表达式：

p = A p

其中p表示网页级别向量，A是链接矩阵。

求网页等级的问题转化为求A的特征向量，于是可以用迭代的方法求出。

给定任意一个初始向量S，不妨设为A，PageRank的计算可以如下

R₀ = S

Loop:

R_i+1 = A R_i

d = ||R_i||₁ - ||R_i+1||₁

R_i+1 = R_i+1 + dE

δ = ||R_i+1 - R_i||₁

while δ > ε

参数d表示迭代的收敛速度，一般取值为0.85。因为链接矩阵巨大，所以改进该算法的瓶颈在于无法用空间换取效率的做法，只有在精度和效率之间作折衷。