PageRank算法的分析及其改进

王德广;周志刚;梁旭

【摘 要】在分析PageRank 算法存在偏重旧网页、主题漂移、网页权值均分、忽视用户浏览兴趣现象的基础上,对其进行改进,考虑网页 【期刊名称】《计算机工程》 【年(卷),期】2010(036)022 【总页数】3页(P291-292,封3)

【关键词】PageRank 算法;搜索引擎;文本数据挖掘;PR 值 【作 者】王德广;周志刚;梁旭

【作者单位】大连交通大学软件学院,辽宁大连,116028;大连交通大学软件学院,辽宁大连,116028;大连交通大学软件学院,辽宁大连,116028 【正文语种】中 文 【中图分类】TP393 1 概述

随着互联网的快速发展，互联网上的信息越来越丰富。网络时代已经到来，上网查找资料的用户呈几何级增长，然而，面临互联网上的海量信息，大多用户都无所适从。什么信息是有用的信息、如何检索信息、如何缩短检索时间是搜索引擎面临的主要问题。传统网络搜索引擎大多是基于关键字匹配的，其查询效果不太理想。Sergey B和Lawrence P借鉴引文分析思想，提出PageRank算法，该算法通过

分析网络的链接结构获得网络中的权威网页，并在搜索引擎 Google中获得成功。随着对PageRank算法的研究深入，许多学者针对其不足，提出了改进。本文对PageRank算法进行了改进。 2 PageRank算法简介

文献[1]提出用于网络链接分析的 PageRank算法，该算法建立在随机冲浪者模型上。具体来说，假设浏览者跟随链接进行若干步的浏览后转向一个随机起点网页又重新跟随其链接浏览，那么一个网页的价值程度值就由该网页被这个浏览者访问的频率决定。

PageRank算法简单描述如下：

u是被研究的网页，vi是指向u的网页， C( vi )是网页vi 的向外指出的网页的链接数，d是规范化因子(一般取0.85)。因此，网页u的PR值计算如下：

3 PageRank算法分析

由于PageRank算法是离线计算网络的PageRank值，在用户查询时仅根据关键字匹配获得网页集合，然后排序推荐给用户，因此具有很高的响应速度，并且搜索引擎 Google中的成功也证明该算法是高效、合理的。但由于仅利用了网络的链接结构，该算法还存在一些缺点：

(1)偏重旧网页：网页存在的时间越长，搜索排序的名次越靠前；

(2)主题漂移现象：无法区分网页中的超链接与网页主题相关还是不相关； (3)平分网页权值：即一个网页被一个权威网页引用和被一个普通网页所引用，其意义与价值是不同的；

(4)忽视用户浏览兴趣：即没有把浏览者这个关键因素考虑进去。 3.1 PageRank算法偏重旧网页的现象

由式(1)可以得出，决定网页 PR(u)值高低的一个主要因素是指向该网页的链接个

数。因为旧网页存在的时间长，被其他网页引用的可能性较高，而实际上新的网页通常包含更新更有价值的信息；如果一个网页刚被放到互联网，可能会由于时间短暂，许多其他网页还没有引用它，导致它的 PR值降低。通过PageRank算法，它出现在搜索页面中的次序通常很靠后，这样可能正好与用户需求相反。因为在很多情况下，用户通常想看到新网页中的最新内容。因此，在某种程度上网页存在时间越长，通过式(1)计算出的网页PR值越高，但却不能很好满足用户的需求[2]。 3.2 PageRank算法的主题漂移现象

PageRank算法出现主题漂移现象的原因主要如下：

(1)PageRank算法无法区分网页中的链接与该网页的主题是否相关，即无法判断网页内容之间的相似相关性，这样容易出现用户搜索的网页内容并不是他想要看的内容；

(2)PageRank算法偏重以.com结尾的网站，因为这类网站通常是综合性网站，可以比其他类型的网站获得更多链接。事实上，这类网页通常涉及的面多而不专，相比之下，某些专业网站对问题的阐述更有权威性且与搜索的主题更贴切。 3.3 PageRank算法的平均网页权值现象

网页的链接分成前向链接和反向链接，而反向链接的数量和质量决定 PR值。反向链接是指所考察的网页被其他网页引用，反向链接数目越多，表示该网页被引用越多，其重要性也越高[3]。但一个网页被权威网站引用和被很多垃圾网页引用，效果是完全不同的。

目前，PageRank算法将当前网页的权值平均分配给它的全部链接。互联网中各个网页的质量价值千差万别，即使是链接在同一个网页上的各个链接，其优劣层次也差很多。所以，PageRank算法这种平均分配权值的方法，在一定程度上影响了网页的排序质量。

3.4 PageRank算法忽视用户浏览兴趣的现象

PageRank算法在设计之初，没有考虑到用户的浏览兴趣，但一个页面能否被用户再次浏览，很大程度上取决于用户的兴趣度。 4 PageRank算法的改进

4.1 对PageRank算法偏重旧网页现象的改进

考虑到大多数“旧网页”都有被引用数目多、内容陈旧、可参考性不高的特点。假设：一个网页被搜索到的时间与其最近一次被修改时间的差值越大，则网页内容的价值越低，权威性就越低。在这个假设下，引入一个与时间有关的权值函数W(t)，与网页的权值呈反比：

其中，W是网页的权值；t为求一个网页被搜索到的时间与其最近一次被修改的时间的差值的函数；d是一个比例常数。得到一级IPR如下：

4.2 对PageRank算法主题漂移现象的改进

通过上文分析可知，传统PageRank算法出现主题漂移现象是因为其无法知道网页中的链接与该网页主题的相关性，所以可以采用文本数据挖掘的方法对网页的内容进行数据挖掘，文本数据挖掘是指从文本数据中抽取有价值的信息和知识的计算机处理技术。文本数据挖掘流程见图1。 图1 文本数据挖掘流程

在这里，引入一个分段函数 F( vi)，用文本数据挖掘出的信息进行处理分级，据此改变其链接权重。函数 F( vi )如下：

对一级IPR算法作进一步的改进：

4.3 对PageRank算法平均网页权值现象的改进

PageRank算法出现平均网页权值的现象，是因为它没有对权威网站和普通网站进行区分[4-5]，权威网站被引用的频率很高，但普通网站被引用的概率却很低。因此，引入网站权威度函数 P( vi)，它是网页被指向链接与指向链接的比：

其中，BackLink为引用网页i的链接数目；InLink为该网页引用其他网页的链接数目；Q为一个与 d相关的常数。在式(5)的基础上得到：

4.4 对PageRank算法忽视用户浏览兴趣现象的改进

网站服务器的Web日志文件中记录了每个用户的访问信息，包含 time-taken字段，该字段描述了页面访问时所用的时间。

定义1 用户获取页面全部内容需要的时间ts，称为页面下载时间。

经统计，在网络畅通时，页面下载时间ts≤3 s，所以，本文设定阈值 ts = 5 s ，若页面下载时间 ts＞ 5 s ，则用户的兴趣度降低。

定义 2 一般人正常阅读完全部页面内容并进行评论及思考所需的时间为tc，称为页面关注时间。tc的计算如下：

其中，Rs是页面正文文字个数；Rc是页面图片个数；Rg是页面视频个数，为了便于计算，将图片和视频转化为文字，设定一张图片相当于50个文字，一个视频相当于100个文字，除以 280是因为成年人的平均阅读速度仅为 280字/min；k是评论系数，取1.21.5。 兴趣度V的计算如下：

其中，tr是用户访问此网页的实际浏览时间； tr/tc为基本兴趣度；(ts-5)×0.1为基本兴趣度的偏移度。

在式(7)的基础上得到IPR4计算如下： 5 实验

为了验证改进算法的效果，用网络爬虫工具 Heritrix在Google上采用

BroadScope模式连续抓取网页10 h，获得约2×105个网页。经过数据预处理，将其导入到数据库中，对100名研究生选取 20个最受关注的话题(见表 1)进行对比实验。

表1 20个关键词列表序号 话题 序号 话题1 反腐倡廉 11 依法行政2 医疗改革 12 三农问题3 食品安全 13 安全生产4 收入分配 14 城乡统筹5 就业问题 15 金融危机6 环保问题 16 社会稳定7 住房问题 17 股市稳定8 教育公平 18 灾后重建9 社会保险 19 机构改革10 司法公正 20 文化创新

本文首先根据未改进的 PageRank算法计算出所有网页的PR值，然后对20个被选话题进行测试，在每个话题返回被搜索到的前50个结果中，统计符合被测试研究生兴趣的网页数目；然后根据改进算法计算出所有网页的 IPR值，用第1次生成的20个话题同样进行测试。符合被测试研究生兴趣的网页数目如图2所示。 图2 算法改进前后结果比较

由图2可见，用PageRank算法查询结果的满意度的平均值为 51.4%左右，而用改进算法把查询结果的满意度提高到71%左右，即改进算法可以更加准确地判断网页的权威性，返回更符合用户查询条件的网页。这个实验结果与实验所选的关键词及实验调查人群的情况有关，今后将在不同背景的人群中收集数据，以进行更全面的验证。 6 结束语

本文通过对PageRank算法的研究，找出该算法的缺陷，并针对其提出具有四级改进算法，通过引入时间权值函数W、分段函数F、网页权值比例函数P及兴趣

度V，有效地解决了传统PageRank算法容易出现的偏重旧网页、主题漂移、网页权值均分、忽视用户浏览兴趣的缺陷，提高了网页的排序质量，从而提升搜索结果的准确性。实验证明，改进算法较PageRank算法在排序质量上有显著提高。 参考文献

[1]张 蓉. Web挖掘技术研究[J]. 计算机工程, 2006, 32(15): 4-6.

[2]焦金涛. 基于 PageRank的 Web挖掘改进算法[J]. 计算机工程,2009, 35(15): 284-285.

[3]田 甜. 基于 PageRank算法的权威值不均衡分配问题[J]. 计算机工程, 2007, 33(18): 53-55.

[4]杨 彬. 基于概念的权重PageRank改进算法[J]. 情报杂志, 2006,(11): 70-72. [5]葛 玲. 基于共现词查询的主题爬虫研究[J]. 计算机工程, 2010,36(8): 286-288.