计jl享机应用 竖些查 堡垒 坐 塑 Page Ra n k算法 的分 析及 实现 ● 金 迪 马 衍 民 摘 要：随着网络信息量的不断增长，搜索引擎技术随之诞生。如何使搜索引擎搜 索的信．E-更加准确、快速 ．成为这 f1技 术主要解决的 问题之一。 Pagegank算法是 根据 网 页间链接 关 系对 网页评 分的 算 法之 一 ，本 文首 先将 对 PageRank算法 进行 分析 ；然后 对其 算 法进行 建模 。 关键 字 ：PageRank算 法 ；网 页 ：链接 人们在 网上 冲浪 的过程 中，常常 从一个起 始 网页开始 ，之 后被那 些带 有链接 文 的 PageRank值 用于衡量 网页的重要 性 。 字所 描述的 网页吸 引 ，从 而点击并打开 另一个 网页。并依次往 复 ，直 到对冲浪感觉 厌 倦 ，而正是 由于 网页和网页通过链 接关系构 成的这个 网络 使得网上 冲浪成 为可能 。 然而知道 Cooke提 出了 PageRank模型 ，这 种网页 问彼此链接关 系的价值 才被挖 掘 从最 后的 PageRank值 可以看 出 ，在 这 3个 网 页中 ，网 页 C的重 要性最 高 。其次 是网 页 A，最后是 网页 B。因为网页 C在这个 局部是被 “认 可”的 ，它被 网页 A和网页 B指向 ；网页 A被 更高级 别的 网页 C“认可 ”，而网 页 B被网 页 A“认 可”，这样 网页 A 出来 ，这种挖 掘过程也称为 “链接 分析”[1】。简单 的说 ，如果 网页 A链 接到 B，那么 表 示网页 A的编写者对 网页 B的一种认 可。或 者说网页 A为网页 B投 了一 票 ，网页 B 的重要性被 网页 A认 可[2】。下 面将对 PageRank算 法定义 ，PageRank算法 在计算 机 和网页 B同样具有 一个 Backlink。由于 网页 C的级别 大于 网页 A．因此 最终 网页 A 的重要性 大于网 页 B。 二 、PageRank的计 算方法 中的计算方法和软件 实现做详细 的说明。 一 、 PageRank算 法定义 PageRank的简单 计算方 法如 图 1-1所示 ，网页 1被 3个 箭头所 指 向，假 定共计 得到 了 100分 。然后 通过链 接平均将 这 1130分 均分给 它所指 向的两个 网页 ，网 页 2 和网页 3。平 均分配是 因为点击两个链 接的可能性 是相等 的。由指定关 系得 到一定 的分 数 ，通 过计算 每个 网页得 到分数 的多少评 价 网页重要性 的方法 ，就是 PageRank 的基本设 计方法 。 图 1·1PageRaak 计 算 方 法 图 网 页是彼此相 连的 ，所 以分数会 不断传 递 下去 ，但 PageRank的计 算是 收敛 的 ， 如图 l一2所 示 ，通 过对三个 网页分别 计算它 们的 PageRank的一个迭代 收敛的例子 。 由图 1-2可以看 到这 3个 网页的分数 之和无 论如何 循环总 是 1，这种特 性在数 学上称 为“不变 分布”，这也是 PageRank计算收敛 的原理 。 PageRank计 算见公式 (1一1)。 ；呵页 A 页 B PRn(A)_(1一 (∑：， (1．1) 说明 。 (I)PR )：网页 A的 PageRank值。 (2)PRn一1㈣ ：网页存在指 向 A的链接 ． 并且网页在 上一次迭代 时的 PageRank值 。 在实 际应用 中可采用幂法来 计算 PageRank。PageRank公式 可以转换为求 解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，则有P『．f0 0 1 f，然后将每一行除以该行非零数字之和。则得到矩阵P『_ 『0 1 1 1 【 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矩阵计算过 程。 由P：I1／2 0 0 I．并且 eer／m=l1／3 I／3 1／3 I，设 d=0．5，这样得到A= f0 0 ] 【 1／2 1 0 J f1／3 1／3 113 1 【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)。 另一方面，网页存在明确的指向网页A的链接，因此 (∑：， )的分数 分配给网页 A。 PageRank可 以通 过迭代计算 的方法得到 ，图计算 的过程如 表 1-1所示 。 表 1·1 PageRank迭 代 计 算 过 程 选 代 次 数 PR(A、 PR ) PR(C) (3>循环迭代 计算 PageRank的过程 f1／6 1／6 2／3 1 『1 1 f1／6+116+2／3 1 f1 1 第1步 Ax：I 5112 116 1／6 1 I：l5／12+1／6+116 140．75 1．r L5／12 2／3 1／6 J L1 J L5／12+2／3+1／6 J L1．25 J 因为 X与 r的差别较 大。继续 迭代 。 f1／6+l／6+2／3 1 1 1 r1．125 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． 125 J 反 复迭代后计算 结果依 次为 r1．0625 1 r1．078125 1 r1．078125 1 r1．0769 1 r1．0769 1 10．78125 I,L0．765625 1，10．769531 ，l0．76923 1,10．76923 l。 L1．15625 J L1．15625 J L1．152344 J L1．1538 J LI．1538 J 直到 最后两次 的结果相近 或相 同的情 况下迭代结 束 。 0 7 5 O ，5 O 78I25 0 76525 0 769531 0 769531 0 769043 0 769287 0 769226 l 25 l l25 I I 5625 1 l 5625 1 1 5234 1 1 5543 1 1 538l l l 538l 1 l 5387 这里的初 始向量 为 s=【l，1，l】 ，表示每 个网 页的初 始 PageRank值均 为 1，到 达第 7次迭代时 ，迭代结果 和第 6次迭代 的结果基本 相同 ，因此迭代可 以停止 。这 种稳定 以上 是对 PageRank算 法 的分析 及建模 ，其 实现 可写入建 立搜索 引擎 的 Lucene 软件包 中 ，或作 为独立开 发的搜索 引擎的排序算 法 。其算 法可使搜索 的排序结果 更 加合理 ，符合用 户的需求 。 【11李刚． ax+Lucene构建搜 索引擎．人 民邮电 出版社 ．2006 【2]g PageR．ank Pro一种 改进 的网页排序 算法，吉林大 学学报 ，2003。41(2)：175-179 (作者单位 ：哈 尔滨商业大 学计算机与信 息工程学 院 ) l18 ·