PageRank 算法的分析及实现


计jl享机应用 竖些查 堡垒 坐 塑 Page Ra n k 算法的分析及 实现 ● 金 迪 马 衍 民 摘 要:随着网络信息量的不断增长,搜索引擎技术随之诞生。如何使搜索引擎搜 索的信.E-更加准确、快速 .成为这 f1技 术主要解决的 问题之一。 Pageg ank 算法是根据网页间链接关系对网页评分的算法之一,本文首先将对 PageR ank 算法进行分析;然后对其算法进行建模。 关键字:PageR ank 算法;网页:链接 人们在网上冲浪的过程中,常常从一个起始网页开始,之后被那些带有链接文 字所描述的网页吸引,从而点击并打开另一个网页。并依次往复,直到对冲浪感觉厌 倦,而正是由于网页和网页通过链接关系构成的这个网络使得网上冲浪成为可能。 然而知道 Cook e 提出了PageR ank 模型,这种网页问彼此链接关系的价值才被挖掘 出来 ,这种挖掘过程也称为“链接分析”[1】。简单的说,如果网页 A 链接到 B ,那么表 示网页 A 的编写者对网页 B 的一种认可。或者说网页 A 为网页 B 投了一票,网页 B 的重要性被网页 A 认可[2】。下面将对 PageRank 算法定义,PageR ank 算法在计算机 中的计算方法和软件实现做详细的说明。 一 、 P ageR ank 算 法定义 PageR ank 的简单计算方法如图 1-1 所示 ,网页 1 被 3 个箭头所指向,假定共计 得到了 100 分。然后通过链接平均将这 1130 分均分给它所指向的两个网页,网页2 和网页 3。平均分配是因为点击两个链接的可能性是相等的。由指定关系得到一定 的分数,通过计算每个网页得到分数的多少评价网页重要性的方法 ,就是 PageR ank 的基本设计方法。 图 1·1PageR aak 计 算 方 法 图 网页是彼此相连的,所以分数会不断传递下去,但 PageR ank 的计算是收敛的, 如图 l一2 所示,通过对三个网页分别计算它们的 PageRank 的一个迭代收敛的例子。 由图 1-2 可以看到这 3 个网页的分数之和无论如何循环总是 1,这种特性在数 学上称为“不变分布”,这也是 PageR ank 计算收敛的原理。 PageR ank 计算见公式(1一1)。 ;呵页A 页B PRn(A)_(1一 (∑:, (1.1) 说明 。 (I)PR ):网页A 的 PageR ank 值。 (2)PRn一1㈣ :网页存在指向A 的链接. 并且网页在上一次迭代时的PageRank 值。 另一方面,网页存在明确的指向网页A 的链接,因此 (∑:, )的分数 分配给网页 A 。 PageRank 可以通过迭代计算的方法得到 ,图计算的过程如表 1-1 所示。 表 1·1 PageR ank 迭 代 计 算 过 程 选 代 次 数 PR (A 、 PR ) P R (C ) 0 7 5 O ,5 O 7 8 I2 5 0 7 6 5 2 5 0 7 6 9 5 3 1 0 7 6 9 5 3 1 0 7 6 9 0 4 3 0 7 6 9 2 8 7 0 7 6 9 2 2 6 l 2 5 l l 2 5 I I 5 6 2 5 1 l 5 6 2 5 1 1 5 2 34 1 1 5 5 4 3 1 1 5 3 8 l l l 5 3 8 l 1 l 5 3 8 7 这里的初始向量为s=【l,1,l】 ,表示每个网页的初始 PageR ank 值均为 1,到达第 7 次迭代时,迭代结果和第 6 次迭代的结果基本相同,因此迭代可以停止。这种稳定 的 PageRank 值用于衡量网页的重要性。 从最后的 PageRank 值可以看出,在这 3 个网页中,网页 C 的重要性最高。其次 是网页A ,最后是网页B 。因为网页 C 在这个局部是被“认可”的,它被网页A 和网页 B 指向 ;网页 A 被 更高级 别的 网页 C “认可 ”,而网 页 B 被网 页 A “认 可”,这样 网页 A 和网页 B 同样具有一个 Backlink。由于网页C 的级别大于网页 A .因此最终网页 A 的重要性 大于网 页 B 。 二、P ageR ank 的计算方法 在实际应用中可采用幂法来计算 PageRank。PageR ank 公式可以转换为求解ljm A¨x 的值,其中矩阵为 A=d P+(1一d)*ee~/m 。d 为阻尼系数,P 为概率转移矩阵,eT为 n 维的全 1行,m 为全部网页个数。 幂法计算过程为 : x 壬意一个初始向量 if(1lx-r【I】< £,返 回 r else x g0t0 2 如图 1-2 的计算过程为: (1)P 概率转移矩阵的计算过程。 初始化一个矩阵 P ,若网页i存在一个指向网页J的链接。则 。= 1;否则等于 『0 1 1 1 0,则有P 『.f0 0 1 f,然后将每一行除以该行非零数字之和。则得到矩阵P 『_ 【 l o o J f0 1/2 1/2 1 1 0 0 l I这个矩阵记录了每个网页跳转到其他网页的概率。采用P ’的转置矩 【 l o o J f0 0 1 ] 阵进行计算,即P l1/2 0 0 f也就是上面提到的概率转移矩阵P。 【1/2 l 0 J (2)A 矩阵计算过程。 f0 0 ] f1/3 1/3 113 1 由P:I1/2 0 0 I.并且eer/m = l1/3 I/3 1/3 I,设d= 0.5,这样得到A= 【 1/2 1 0 J 【l,3 l,3 l/3 J f1『6 l,6 2 ,3 1 l 5/12 1/6 116 I,初始每个网页的PageRank值均为1,即x‘=(1,1,1)。 (3>循环迭代计算 PageR ank 的过程 f1/6 1/6 2/3 1 『1 1 f 1/6 + 116 + 2/3 1 f1 1 第1步 Ax:I 5112 116 1/6 1 I:l5/12+1/6+116 14 0.75 1.r L5 /12 2/3 1/6 J L1 J L5/12 +2/3 + 1/6 J L1 . 2 5 J 因为 X 与r 的差别较大。继续迭代。 f1/6 + l/6+ 2/3 1 1 1 r1.12 5 1 第2步Ax:【5/l2+l,6+1,6 I· .75 I:lo_75 I-r' L5 /12 + 2/3 + 1/6 J L1 . 25 J L1 . 12 5 J 反复迭代后计算结果依次为 r 1.0 62 5 1 r 1.0 78 12 5 1 r1.07 8 125 1 r1.0 76 9 1 r1.07 69 1 10.78125 I,L0.765625 1,10.769531 ,l0.76923 1,10.76923 l。 L 1.156 2 5 J L 1.156 25 J L1.15 23 44 J L1.153 8 J LI.15 3 8 J 直到 最后两次 的结果相近 或相 同的情 况下迭代结 束 。 以上是对 PageRank 算法的分析及建模,其实现可写入建立搜索引擎的Lucene 软件包中,或作为独立开发的搜索引擎的排序算法。其算法可使搜索的排序结果更 加合理,符合用户的需求。 【11李刚. ax+ Lucene 构建搜索引擎.人民邮电出版社.2006 【2]g PageR.ank Pro 一种改进的网页排序算法,吉林大学学报,2003。41(2):175-179 (作者单位:哈尔滨商业大学计算机与信息工程学院) l 18 · " , 撩

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

alonlong

贡献于2015-03-02

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf