信息检索之Pegerank算法

《信息检索之Pegerank算法》由会员分享，可在线阅读，更多相关《信息检索之Pegerank算法（4页珍藏版）》请在金锄头文库上搜索。

1、信息检索的排序方法信息检索的排序方法一、一、Hilltop 算法算法 二、二、ExpertRank 三、三、HITS 四、四、TrustRank 五、五、PageRank 概念概念PageRank 是 Google 专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而 言的重要程度。它由 Larry Page 和 Sergey Brin 在 20 世纪 90 年代后期发明。PageRank 实 现了将链接价值概念作为排名因素。 PageRank 将对页面的链接看成投票，指示了重要性。 算法算法PageRank 让链接来“投票“ 一个页面的“得票数”由所有链向它的页面的重要性来决定，到一

2、个页面的超链接相当于 对该页投一票。 一个页面的 PageRank 是由所有链向它的页面（“链入页面” ）的重要性经过递归算法得到 的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么 它没有等级。 指标指标Google 工具条上的 PageRank 指标从 0 到 10。它似乎是一个对数标度算法，细节未知。 PageRank 是 Google 的商标，其技术亦已经申请专利。 PageRank 近似于一个用户，是指在 Internet 上随机地单击链接将会到达特定网页的可能性。 通常，能够从 更多地方到达的网页更为重要，因此具有更高的 PageRank。每个到其他网页

3、的链接，都增 加了该网页的 PageRank。具有较高 PageRank 的网页一般都是通过更多其他网页的链接而提高的。 为了查看站点 PageRank，请安装 GOOGLE 工具条并启用 PageRank 特性，或者在 firefox 安装 SearchStatus 插 件。但是请注意，GOOGLE 所指示的 PageRank 是个缓冲值，通常是过时的 更新频率更新频率PageRank 值每年只发布几次，有时就得使用过时信息，因此，PageRank 并不是一个非常精确的度量。 GOOGLE 自己也似乎在使用更精确的值来进行排名。 在 GOOGLE 使用来构造搜索结果页面的采集算法中，Page

4、Rank 只是其中的一个因素。有 可能在特定查询下，具有较低 PageRank 的页面仍然能够排在具有较高 PageRank 的页面前 面。PageRank 也不一定是相关的，它使用链接来衡量整体受欢迎程度，而不是使用相关主 题。目前 GOOGLE 在计算搜索排名时也考虑链接的相关程度，因此 PageRank 不应该成为 搜索引擎营销的唯一重点。构建相关链接，通常也自然会带来较高的 PageRank。此外，为 了提高 PageRank 而特意构建太多的不相关链接也有可能损害站点的排名，因为 GOOGLE 试图检测并对不相关链接降分，认为这种链接是用于提高排名得分的。 PageRank 还被用户

5、广泛认为是站点可靠的因素，因为用户倾向于相信带有较高值的站点更 为著名或权威。当然，这就是 PageRank 所设计的目标。这个概念是 GOOGLE 所认可的， 因此 GOOGLE 通过减少或清零 PageRank 来惩罚那些垃圾或不相关站点 Pegerank 算法的实现过程算法的实现过程PageRank 是 Google 公司的拉里佩奇（Larry Page）等人提出的链接分析 算法，算法也以佩奇的姓氏命名为“PageRank” 。PageRank 是根据万维网超链 接关系对网页重要程序进行估计的算法，相关技术在 2008 年 1 月申请了美国专 利，并在同年谢尔盖布林和拉里佩奇的论文“大规

6、模超文本万维网搜索引 擎的架构” （The Anatomy of a Large-Scale Hypertextual Web Search Engine）中首 次被公开。 PageRank 依靠万维网链接结构分析对网页个体的质量进行评估，算法将从 页面 A 到页面 B 的超链接作为 A 向 B 的一次投票，但并非简单地靠统计票数来 衡量质量高低，算法还充分考虑了投票者的因素，本身较“重要”的网页的投 票会更受重视。显然这样计算出的网页质量评估结果比单纯依靠入度的评估方 式更为合理，因为后者实质上是认为链接向当前页面的各个页面的地位是平等 的，这是一个不符合万维网实际情况的假设。 PageRa

7、nk 是一种衡量“网页质量”的方式，由于“质量”的定义本身带有 很强的主观性，因此“网页质量”的定义也千差万别，可以从时效性、页面结 构组织、独特性等不同角度加以定义，而 HITS 算法使用的“链接权威度”与 “内容权威度”也是一种“网页质量”的定义方式。对于 PageRank 而言，它使 用用户随机浏览互联网时访问到某个页面的概率大小作为此页面的“质量”的 定义。 PageRank 算法所建立的用户浏览模型被称为“随机游走” （random walk） 模型。用户使用一个特殊的浏览器来浏览网页，这个浏览器没有地址栏、后退 按钮，即只能顺着网页链接浏览。同时提供一个“随便逛逛”的功能，可以通

8、过点此按钮随机打开万维网上的一个网页开始浏览。那么，网页 A 被访问的概 率可以用如下公式计算得到： APiiiPreeOutPPageRank NAPageRank)(deg)()1 (1)(上式右半部分是使用“随便逛逛”功能访问到页面 A 的概率，而后半部分则是 使用超链接访问到页面 A 的概率，两者相加即为访问到页面 A 的总概率大小。 可知，如果给定参数 ，页面 A 的 PageRank 值事实上是由链接到它的各个页面的 PageRank 值决定的。其计算过程与 HITS 算法的计算过程类似，也是一个迭 代计算的过程，算法流程如下所示 PageRank（简化）算法（简化）算法 （1）取

9、万维网链接结构图 G，G 的规模为 N，则 G 中包含 N 个结点。对于 G 中的每一个结点 n，设 PR(n)是其 PageRank 值，而向量为 G 对应的 PageRank PR结果向量。（2）设定，即：对 G 中每一个节点 n，设定其初始值 PR(0)(n)均)1,.,1,1,1(NNNNPR 为。N1（3）For k=1,2,3,TN 对 G 中每一个节点 n， nPiik kiPreeOutPPR NnPR)(deg)()1 (1)()1( )(其中， 为预先设定的参数，Outdegree(Pi)为页面 Pi的出度值。（4）当结果向量收敛时，返回（3）继续循环；当收敛时，算法结束，

10、输出所计 PR PR算出的 G 中每一个节点 n 的 PR(n)的结果。 上述算法要求 G 中不存在没有超链接的“死胡同”网页，为解决这一问题，可 以采用如下算法 ageRank（标准）算法（标准）算法 （1）取万维网链接结构图 G，G 的规模为 N，则 G 中包含 N 个结点。对于 G 中的每一个结点 n，设 PR(n)是其 PageRank 值，而向量为 G 对应的 PageRank PR结果向量。2）设定，即：对 G 中每一个节点 n，设定其初始值 PR(0)(n)均为)1,.,1,1,1(NNNNPR ，同时设定临时变量。N1),.,(NNNNI（3）For k=1,2,3,M 对 G

11、 中每一个节点 n， 若 Outdegree(n)0，则有：，iPiPnif)(deg)()1 ()()()1(nreeOutnPRPIPIkii 若 Outdegree(n)=0，则有：，GPiNnPRPIPIkii)()1 ()()()1( 其中， 为预先设定的参数，Outdegree(Pi)为页面 Pi的出度值。将临时变量赋值给： PR IPRk)(临时变量赋初值：),.,(NNNNI（4）当结果向量收敛时，返回（3）继续循环；当收敛时，算法结束，输出所计 PR PR算出的 G 中每一个节点 n 的 PR(n)的结果。可以看出，与简化算法相比，标准算法考虑到没有超链接可以看出，与简化算法

12、相比，标准算法考虑到没有超链接网页的情况，对这部分网页，网页的情况，对这部分网页， “随机游走随机游走”的浏览方式则只的浏览方式则只能点击能点击“随便逛逛随便逛逛”功能进行跳转，而任何功能进行跳转，而任何 G 中的网页都中的网页都可能成为跳转目标。因此步骤（可能成为跳转目标。因此步骤（1）中需要在）中需要在 G 的网页集合的网页集合中均分这部分中均分这部分“死胡同死胡同”网页的网页的 PageRank 值。事实上，这值。事实上，这相当于先在相当于先在“死胡同死胡同”网页和网页和 G 中的所有网页两两之间添中的所有网页两两之间添加了一条虚拟的超链接，之后，再在这个经过修改的链接加了一条虚拟的超链接，之后，再在这个经过修改的链接关系图上进行简化算法。关系图上进行简化算法。