搜索引擎PageRank算法的改进

  本文关键词：搜索引擎PageRank算法的改进，由笔耕文化传播整理发布。

改进的PageRank算法在搜索引擎中的应用

计 算 机 工 程 第 35 卷 第22期

Vol.35 No.22 Computer Engineering ·软件技术与数据库·

文章编号：1000—3428(2009)22—0035—03

文献标识码：A

2009年11月

November2009

中图分类号：TP391

搜索引擎PageRank算法的改进

杨劲松，凌培亮

(同济大学机械工程学院，上海 200092)

摘 要：为了解决企业快速决策时信息检索的问题，，提出一种改进的PageRank算法。在考虑网页产生时间因素的同时，通过锚文本与网页主题的相似度分析按权重分配网页各正向链接PageRank值，产生的PageRank值更贴合主题搜索引擎的要求，并保持算法的简洁性。实验结果证明该改进算法能有效减少主题漂移现象，恰当提升新网页PageRank值。 关键词：搜索引擎；锚文本；向量空间模型

Improvement of PageRank Algorithm for Search Engine

YANG Jin-song, LING Pei-liang

(College of Mechanical Engineering, Tongji University, Shanghai 200092)

【Abstract】In order to solve the problems in information retrieval when enterprise making rapid decision, this paper proposes an improvedPageRank algorithm. Considering the time factor by Web page, it distributes the forward link different PageRank value based on the proportion bythe similarity analysis between anchor text and Web page text. The final PageRank value is more suitable for topic-specific search engine and keepssimplicity of algorithm. Experimental result shows that the improved algorithm can effectively reduce the phenomenon of topic-drift and enhance thePageRank value of new Web page.

【Key words】search engine; anchor text; Vector Space Model(VSM)

面对持续膨胀的海量互联网资源，目前通用搜索引擎(General Search Engine, GSE)的信息检索无法完全满足企业快速决策的信息需求，主题搜索引擎(Topic-specific Search Engine, TSE)应运而生并引起研究者的重视。本文结合主题搜索引擎的使用需求，使改进的PageRank算法适应于主题搜索引擎，并进行实验验证。

1 PageRank算法研究现状

Google使用PageRank算法[1]构造的搜索引擎获得了巨大成功。简单的说，PageRank是代表互联网上某个页面重要性的一个数值，该值仅仅依赖于网络的链接结构。PageRank 算法的具体思路是将某个页面的PageRank值除以存在于该页面的正向链接，由此得到的值分别和正向链接所指向页面的PageRank值相加，得到被链接页面的PageRank值。算法基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关系判定所有网页的重要性。若一个网页的得票越多，则认为它的重要性也越高，投票网页的重要性决定了票的重要程度。

当计算某个网页PageRank值时考虑所有的反向链接，页面u的PageRank值计算公式如下：

PR(u)=(1 d)+d×∑

PR(v)

(1)

v∈B(u)Nv

其中，PR(u)代表页面u的PageRank数值；B(u)代表有链接

直接指向页面u的网页集；Nv表示网页v正向链接的数量；

PR(v)

表示网页v将自己的PageRank值平均分配给自身的正Nv

接浏览，而不产生随机跳跃的概率值，在实际应用中，加入阻尼系数d能保证计算结果总是收敛。

由式(1)可知，计算某个网页的PageRank值总是依赖于其他的相关页面，在实际计算PageRank值时大都采取迭代法，递归地用给定矩阵乘以一个任意初始向量，直到其收敛，计算结果的精确程度依赖于初值的选取和迭代的次数。由于PageRank值的作用在于给网页排序，因此只要在认为网页排序趋于稳定的时候就可以停止递归计算而不一定要得到实际的PageRank值。在实际运算中，确定网页重要顺序的计算次数比得到准确PageRank值的次数要少得多。

由于PageRank值仅仅依赖于网络的链接结构，网页的PageRank值是按存在于该页面的正向链接数来平均分配的，

容易发生主题因此用于被链接的页面的PageRank值的计算，

漂移现象，在主题搜索引擎应用时该缺陷将非常明显，会使得搜索结果中存在过多与查询主题无关的网页，同时由于网页的PageRank值是由反向链接的数量和质量决定的，因此PageRank算法倾向于旧网页，而企业快速决策非常关注新网页产生时间短，被引用次数少，PageRank值偏低。针对这些缺陷，许多学者提出相应的改进算法，如文献[3]提出一种主题敏感的PageRank改进算法，文献[4]提出一种结合链接分析和文本内容的PageRank改进算法，文献[5-6]分别提出具有时间反馈的PageRank改进算法。上述算法有效地改进了PageRank算法的固有缺陷，但在不同程度上增加了计算的复杂程度和实用难度。本文在研究和分析PageRank算法的基础

作者简介：杨劲松(1976－)，男，讲师、博士研究生，主研方向：搜索引擎，分布式计算；凌培亮，教授、博士

收稿日期：2009-06-12 E-mail：yangjinsong@

向链接[2]；d是阻尼系数，0<d<1，通常取0.85，由于用户

在互联网浏览时可能不按当前页面中的链接前进，而随机跳跃到完全无关页面，因此d实际上代表的是用户跟随网页链

—35—

  本文关键词：搜索引擎PageRank算法的改进，由笔耕文化传播整理发布。