信息检索之pagerank算法

《信息检索之pagerank算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、...一、实验目的u理解PageRank算法的基本思想和原理；u了解链接结构分析的应用和意义（主要是与排序因素的融合）；u了解PageRank的简化算法、标准算法和加速算法的异同及改进办法。二、实验原理及基本技术路线图（方框原理图）PageRank是Google公司的拉里·佩奇（LarryPage）等人提出的链接分析算法，算法也以佩奇的姓氏命名为“PageRank”。PageRank是根据万维网超链接关系对网页重要程序进行估计的算法，相关技术在2008年1月申请了美国专利，并在同年谢尔盖·布林和拉里·佩奇的论文“大规模超文本万维网搜索引擎的架构”（TheAn

2、atomyofaLarge-ScaleHypertextualWebSearchEngine）中首次被公开。PageRank依靠万维网链接结构分析对网页个体的质量进行评估，算法将从页面A到页面B的超链接作为A向B的一次投票，但并非简单地靠统计票数来衡量质量高低，算法还充分考虑了投票者的因素，本身较“重要”的网页的投票会更受重视。显然这样计算出的网页质量评估结果比单纯依靠入度的评估方式更为合理，因为后者实质上是认为链接向当前页面的各个页面的地位是平等的，这是一个不符合万维网实际情况的假设。PageRank是一种衡量“网页质量”的方式，由于“质量”的定义本身带有

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

4、被访问的概率可以用如下公式计算得到：......上式右半部分是使用“随便逛逛”功能访问到页面A的概率，而后半部分则是使用超链接访问到页面A的概率，两者相加即为访问到页面A的总概率大小。可知，如果给定参数α，页面A的PageRank值事实上是由链接到它的各个页面的PageRank值决定的。其计算过程与HITS算法的计算过程类似，也是一个迭代计算的过程，算法流程如下所示：PageRank（简化）算法（1）取万维网链接结构图G，G的规模为N，则G中包含N个结点。对于G中的每一个结点n，设PR(n)是其PageRank值，而向量为G对应的PageRank结果向量。（

5、2）设定，即：对G中每一个节点n，设定其初始值PR(0)(n)均为。（3）Fork=1,2,3,…,TN对G中每一个节点n，其中，α为预先设定的参数，Outdegree(Pi)为页面Pi的出度值。（4）当结果向量收敛时，返回（3）继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的PR(n)的结果。上述算法要求G中不存在没有超链接的“死胡同”网页，为解决这一问题，可以采用如下算法：PageRank（标准）算法（1）取万维网链接结构图G，G的规模为N，则G中包含N个结点。对于G中的每一个结点n，设PR(n)是其PageRank值，而向量为G对应的Pa

6、geRank结果向量。......（2）设定，即：对G中每一个节点n，设定其初始值PR(0)(n)均为，同时设定临时变量。（3）Fork=1,2,3,…,M①对G中每一个节点n，若Outdegree(n)>0，则有：，，若Outdegree(n)=0，则有：，其中，α为预先设定的参数，Outdegree(Pi)为页面Pi的出度值。②将临时变量赋值给：③临时变量赋初值：（4）当结果向量收敛时，返回（3）继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的PR(n)的结果。可以看出，与简化算法相比，标准算法考虑到没有超链接网页的情况，对这部分网页，“随

7、机游走”的浏览方式则只能点击“随便逛逛”功能进行跳转，而任何G中的网页都可能成为跳转目标。因此步骤（1）中需要在G的网页集合中均分这部分“死胡同”网页的PageRank值。事实上，这相当于先在“死胡同”网页和G中的所有网页两两之间添加了一条虚拟的超链接，之后，再在这个经过修改的链接关系图上进行简化算法。三、所用仪器、材料（设备名称、型号、规格等）硬件：PC机一台操作系统：Windows7编程语言：JavaIDE：eclipse3.5.2四、实验方法、步骤......编程实现PageRank算法，能够对测试数据计算PageRank算法，并输出每次迭代的计算结果

8、。要求给出详细的算法设计过程五、实验过程原始记录(数