浅析网页搜索引擎的PageRank排序算法

欧贤

摘 要 随着Internet 技术的快速普及和迅猛发展，Web 上信息总量日益膨胀。用户如何从网页信息中快速获取所需信息变得日益重要。本文对Web结构挖掘算法PageRank 算法进行研究学习，分析了其两种算法的基本思想和技术特点。

关键词 排序 PageRank算法 随机游走

中图分类号：TP393 文献标识码：A

1 PageRank算法概述

PageRank（网页级别），2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇[1]。它是Google排名运算法则（排名公式）的一部分，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后，Google通过PageRank来调整结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。级别从0到10级，10级为满分。

2 PageRank算法过程分析

PageRank算法所建立的用户浏览模型被称为“随机游走”（random walk）模型。用户使用一个特殊的浏览器来浏览网页，这个浏览器没有地址栏、后退按钮，即只能顺着网页链接浏览。同时提供一个“随便逛逛”的功能，可以通过点此按钮随机打开万维网上的一个网页开始浏览。那么，网页A被访问的概率可以用如下公式计算得到：

上式右半部分是使用“随便逛逛”功能访问到页面A的概率，而后半部分则是使用超链接访问到页面A的概率，两者相加即为访问到页面A的总概率大小。可知，如果给定参数 ，页面A的PageRank值事实上是由链接到它的各个页面的PageRank值决定的。

3 PageRank算法

PageRank算法要求G中不存在没有超链接的“死胡同”网页，为解决这一问题，可以采用如下算法：

（4）当结果向量收敛时，返回（3）继续循环；当收敛时，算法结束，输出所计算出的G中每一个节点n的PR（n）的结果。

4.总结

可以看出，与第一种算法相比，第二种算法考虑到没有超链接网页的情况，对这部分网页，“随机游走”的浏览方式则只能点击“随便逛逛”功能进行跳转，而任何G中的网页都可能成为跳转目标。事实上，这相当于先在“死胡同”网页和G中的所有网页两两之间添加了一条虚拟的超链接，之后，再在这个经过修改的链接关系图上进行简化算法。

参考文献

[1] 黄德才，戚华春，钱能.基于主题相似度模型的TS2PageRank算法[J].小型微型计算机系统，2007（03）.

[2] 卢开澄.计算机密码学——计算机网络中的数据保密与安全（第3版）[M].清化大学出版社，2002.

[3] 李凯，赫枫龄，左万利.PageRank2Pro一种改进的网页排序算法[J].吉林大学学报，2003（4）.