PDF《一种改进的 PageRank 算法》

计算机系统应用http://www.

c-s-a.org.cn

2012 年第21 卷第2期214 经验交流 Experiences Exchange 一种改进的PageRank 算法 ① 古文丽,陈玮,陈娇,陆晓野 (上海理工大学 光电信息与计算机工程学院,上海 200090) 摘要:研究了现有的基于链接结构的 PageRank 算法.结合网页链接分析和网页内容相关性分析提出了一种改 进的 PageRank 算法,从分析网页内容相关性的角度解决相关性需求,从网页链接分析的角度解决权威性需求, 并且实验证明,改进的 PageRank 算法优于传统的 PageRank 算法的排序结果. 关键词:PageRank;

网页排序;

链接分析;

文件相关性 Improved PageRank Algorithm GU Wen-Li, CHEN Wei, CHEN Jiao, LU Xiao-Ye (School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200090, China) Abstract: This paper researched the PageRank algorithm based on the existing link structure and proposed a modified PageRank algorithm, combining the analysis of webpage analysis and Web content analysis. The relevance and authority algorithm demands are met by analyzing the similarity of the contents of Web pages and the link structure respectively, and experiments show that the improved PageRank algorithm is superior to the traditional approach in terms of ordering results. Key words: PageRank;

Web page ranking;

link analysis;

document relevance;

information retrieva 随着 Web 数据的急剧增长,搜索引擎成为用户获 取信息的重要工具.Internet 已成为世界上最丰富和最 密集的信息来源.然而,这些大量无序的信息也给信 息检索带来了很多的问题.如何让用户先获得最权威 和查询最相关的网页,是目前迫在眉睫的问题,也是 搜索引擎商业运行成功的关键.如何把查询最权威、 最相关的搜索结果页中的网页排到最前列是解决这个 问题的关键.要解决这个问题,就要充分利用网络的 各种信息,包括网络链接,网页内容和用户访问离开 的信息.受欢迎的传统的 PageRank[1] 和HITS[2] 算法是 简单的从排序分析的角度,而忽略了网站和其他的信 息,故很难得到较好的排序结果.

1 PageRank算法介绍 PageRank 的基本思想:如果一个页面被其他许多 页面引用,则这个页面可能是重要页面;

一个页面尽 ① 收稿时间:2011-05-27;

收到修改稿时间:2011-06-09 管没有被多次引用,但被一个重要页面引用,那么这 个页面可能也是重要页面;

一个页面的重要性被平均 分配并传递到它所引用的页面.PageRank 技术基于整 个Web 的链接结构来计算各网页的重要性,它认为用 户能够通过网页之间的超链接访问到整个网络. PageRank 计算公式可以表示如下: ( ) v B u R u c R v N v ? = ? (1) 构造有向 Web 图G=(V,E) ,其中顶点 V 为所 有网页集合,边E为网页间的链接集合,网页 A 中有 指向网页 B 的链接表示顶点 A、B 间存在一条边,则 公式(1)中B(u)表示直接指向网页 u 的网页集合(u 的入链网页的集合;

N(v)表示网页 v出链网页的数量) , R(v)/N(v)是指网页 v 把自己的 PageRank 值平均分配给 自己网页中的出链网页,c=1[3] . 互联网中可能存在这样的情况:有一组网页互相

2012 年第21 卷第2期http://www.c-s-a.org.cn 计算机系统应用Experiences Exchange 经验交流

215 之间是彼此链接的,但都没有对组外网页的链接,这样,一旦有组外网页链接到组内的网页,由于在组内 不存在对外的链接, 因此传递过来的 PageRank 值就一 直滞留在这组网页内部,不能传递出去,这就是 PageRank 值沉淀现象 (LinkSink) . 为了避免沉淀现象, 对公式(1)引入一个阻尼系数 d,使其变为: ( ) ( ) (1 v B u R u d d R v N v ? 2) PageRank 计算公式可以从概率的角度解释为一 个随即的网页浏览者随机选择一个网页后,不断的点 击网页上的连接,但是从不返回;