基于主题特征和时间因子的改进PageRank算法

8662010,31(4)计算机工程与设计Computer Engineering and Design

0引言

目前对实现网络信息挖掘的代表性算法是基于链接结构

的PageRank和HITS算法，忽略了网页的主题特征和网页存

在的时间，因此，搜索的效果不理想[1]。根据前人的研究结果，

网络上的网页具有两个主题特征：

(1)Hub特征[2]，即网络上的网页具有权威性；

(2)Linkage/Sibling Locality特征[3]，即网络上的网页的分布

具有相关性。本文从网页的主题特征和时间特征的角度改进

了PageRank算法。

1算法分析

1.1PageRank算法

PageRank算法源自于传统的文献引文分析法，即可以通

过计算其它文献对该文章引用的数量来衡量该文献的质量，

该文献在其它文献中被引用的次数越多，则该文献的质量就

越高；同理，互联网上某一个网页被其它的网页引用的次数越

高，那么同理认为该网页的重要性也越高。通过揭示互联网

上网页相互之间的引用关系(即链接结构)，可以衡量出该网页

在互联网上的重要程度(即PageRank值)[4]。

根据这个原理，某一网页PageRank值经典的计算方法如

公式(1)所示。

１

１

＋(1)

式中：A——互联网上某个待评价的网页，T

1

，T

2

，…，T

i

，…，T

n

则

表示互联网上A的链进网页，C(T

i

)表示A的第i个链进网页T

i

中链出网页的总数；PR(A)、PR(T

i

)分别表示网页A和它的链进

网页T

i的PageRank值，我们简称其为PR值；d为网也之间链

接的阻尼系数，通常为0.85；C

Total为网络上网页的总量。

虽然PageRank算法能够在一定程度上反映出互联网上

网页之间的链接关系，可以有效地从互联网上网页之间的

链接结构中挖掘出网页。但是，PageRank算法仍然存在3

点不足：

(1)没有考虑到不同的网页，质量的高低不同，有些网页在

查询的主题方面具有业内权威性，用户更倾向于获取权威的

网页，而传统的PageRank算法不能体现出网页的权威性；

收稿日期：2009-02-24；修订日期：2009-07-20。

作者简介：段淮川(1985－)，男，江苏阜宁人，硕士，研究方向为计算机控制；胡平(1962－)，男，副教授，硕士生导师，研究方向为过程控制。E-mail：aduan85@https://www.sodocs.net/doc/0b16032763.html,

基于主题特征和时间因子的改进PageRank算法

段淮川，胡平

(南京工业大学信息科学与工程学院，江苏南京210009)

摘要：经典PageRank算法单纯地考虑到对网页的链接结构进行分析，而不能考虑到网页在搜索主题方面的相关性和权威性，以及用户对新旧网页的依赖程度的不同。针对经典PageRank算法存在的上述缺陷，综合网页的主题特征和时间特征两个因素，提出了一种改进的PageRank算法WTPR(weighted topic PageRank)。该算法通过网页链接分析和内容分析来解决网页的权威程度和相关程度，通过时间因子实现PageRank值随时间的变动而浮动。仿真结果表明，改进后的算法与PageRank算法相比获得了更好的效果。

关键词：主题特征;时间因子;PageRank;相关性分析;链接

中图法分类号：TP391.3文献标识码：A文章编号：1000-7024(2010)04-0866-03

Improved PageRank algorithm based on topic character and time factor

DUAN Huai-chuan,HU Ping

(College of Information Science and Engineering,Nanjing University of Technology,Nanjing210009,China) Abstract：The famous ranking algorithm PageRank just analyzed the link structure of web pages,but did not consider the relativity and authority of web pages,as well as the different degree of people’s depending on new web pages and old Web pages.To improve the limitations described above all,the weighted topic PageRank(WTPR)algorithm is presented,combining with topic character and time character.Authority and relevance degree are met by analyzing the link structure and contents of web pages respectively;PageRank value fluctuating with time is met via time character.Experimental results show that the improved algorithm performs better than the fa-mous PageRank algorithm.

Key words：topic character;time factor;PageRank;relativity analysis;link

计算机工程与设计Computer Engineering and Design

段淮川，胡平：基于主题特征和时间因子的改进PageRank 算法

2010,31(4)867

(2)PageRank 算法单纯地考虑到对网页的链接结构进行分析，没有分析网页中的内容和用户查询的主题是否相关，以及相关程度如何。因此，常常导致抓取到的网页虽然具有较高的PageRank 值，却与主题无关或相关程度很小的现象(也就是主题漂移现象)发生；

(3)PageRank 算法在计算网页的PageRank 值时，对新旧网页都只考虑网页的链接关系，而一些新发布的网页在短期内不能被链接引用，计算出来的PageRank 值会比旧的网页小的多，导致搜索的结果往往不包含新网页，或者排序在尾部，得不到用户的关注。

1.2相关改进的算法

针对PageRank 算法的第一点缺陷，由Xing 提出的加权

PageRank (WeightedPageRank ，WPageRank )算法[5]，增加了Page-Rank 值中的权威性权重，使得权威性网站更容易被搜索到，但却加剧了主题漂移现象的发生，同时引入了乘法，使得计算复杂，搜索效率降低。

针对第2个不足之处，由Ingongngam 等人提出的以主题为核心内容的PageRank (topic centric ，TCPageRank )算法[6]，解决了网页内容与查询主题之间的相关性问题，忽略了不同网页的重要程度不同。对新的网页计算的PR 值往往很低，导致新网页得不到关注。

2改进PageRank 算法WTPR 算法

综合对上述算法的分析，根据主题网页的特征，从主题权

威性、主题相关性和时间性角度引入了主题预测相关度加权、权威度加权和时间因子。

在原PageRank 算法基础上提出改进PageRank 算法WTPR

算法

１

＋

１

＋

（２）

式中：W s 和W c 分别表示网页T i 的权威性权值和相关性权值；

,

(3)

上式中

，

,

=

(4

)

,

分别是基于出度和入度的权重因子，I (T i )和O

(T i )是某个网页i 的入度和出度。改进算法中对W s 的计算依据主题网页的Hub 特征，采用入度作为权威性权

值，即

=

2

(5)

式中：A ij 和T ij 为某个关键词j 在网页A 和T i 中的权值，该权值一般都采用基于关键词频率统计的TF-IDF 算法来计算，设关

键词j 在i 文档中的权值为W ji ，则sim (j ，i )=tf ji ×lg (N/df j )，其中tf ji 为关键词j 在i 文档中重复出现的次数，df j 表示包含关键词j 的文档总数，N 表示文档总数。

本文算法仍然采用向量空间模型的算法，只是针对HTML 文档的半结构化特性对TF-IDF 进行一定的改进，对于出现在之间、、和、

等标签的关键词我们赋予比其它地方出现的词较高的权重因子，假设关键词j

的权重因子为j

sim (j ，i )。本

文的根据关键词所在位置设定5种情况：①