采用改进受欢迎度的PageRank优化算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇采用改进受欢迎度的PageRank优化算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

文章编号：1003-6199(2011)04-0095-03

摘 要：为了克服搜索引擎在搜索过程中经常重复性地把当前受欢迎的网页放在搜索结果的首要位置，而忽略那些不受大多数用户欢迎的网页的问题，文中提出一个采用改进受欢迎度的pagerank优化算法。该改进算法首先通过建立网页的真实质量函数来纠正搜索引擎的上述问题，然后再采用一个新的网页受欢迎度来消除内在的网页质量问题从而避免该问题。实验结果表明该改进算法在评价网页时获得了较好的公平性，从而能够克服上述搜索引擎的不足。

关键词：搜索引擎;受欢迎度；PageRank优化算法

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

PageRank Optimization Algorithm by Applying Improved Popularity Degree

LI Na,LIU Junhui

(Department of Information Engineering, Zhengzhou College of Animal Husbandry Engineering,Zhengzhou 450011，China)

Abstract:In search process, search engine often repeatedly places currently popular pages at the top of search results and ignores unpopular pages. In order to escape from this problem, a PageRank Optimization Algorithm Based on Improved Popularity Degree (PROABIPD) was proposed. The PROABIPD firstly uses a new page real quality ranking function to correct the above problem, and then employs an improved popularity degree to avoid the problem. Experimental results show that the PROABIPD can attain unbiased web ranking and can overcome the aforementioned deficiency of search engine.

Key words:search engine;popularity degree; PageRank optimization algorithm

1 引 言

PageRank算法［1］是L. Page和S. Brin于1998年提出的一种用于标识网页等级/重要性的算法，同其他网页排名算法相比，该算法具有易于理解、实现简单等优点［2］，这使得PageRank算法成为了众多搜索引擎的首选网页排名算法。

PageRank算法对高质量网页的捕捉能力较强，大多数用户对百度和Google等搜索引擎所返回的查询结果满意程度较高［3］。但是，PageRank算法会出现“富者更富”问题［4］，也即搜索引擎会将高等级网页返给用户，而那些等级低的网页即使它们的质量高也会被大多数用户忽略，并且对那些新产生的高质量网页更是如此，因为刚开始新产生的网页还未被搜索引擎索引。这些网页可能被用户永久忽略，从长期来看，这也会在总体上降低搜索结果的质量［5］。

针对上述问题，本文提出了一个改进的PageRank算法。该改进算法首先通过建立网页的真实质量来纠正搜索引擎的“富者更富”问题，然后再采用一个新的网页受欢迎度来消除内在的网页质量问题从而避免搜索引擎的“富者更富”问题。实验结果表明该改进的PageRank算法在一定程度上能有效消除搜索引擎的“富者更富”问题，使搜索结果更加符合用户的真实需求。

2 PROABIPD所涉及的核心方案

在本文所提的PROABIPD中，PageRank算法以及该算法所涉及的各种参数，需要视具体情况和待解决的实际问题来选取合适的值，这里不做介绍，有兴趣的请参阅文献［6,7］。下面仅详细介绍一下本文的核心方案设计。

2.1 网页真实质量评估函数

网页真实质量评估函数定义为：

Q(p)=P(Lp|Ap)(1)

其中Ap表示用户第一次访问网页p就会对该网页有不错的评价，Lp表示用户喜欢该网页。因此,Q(p)是一个条件概率，表示一个用户在第一次访问网页p时就会喜欢该网页。通过该定义可以假设把网页p展示给所有的用户来测定该网页的质量。例如，在100个用户中，假设有90个用户在访问网页p后会喜欢它，则它的质量Q(p)即为0.9。

该定义是对一个网页真实质量的一个合理的评价标准。在实际中，某个用户可能对一个网页评价很高，而另一用户可能觉得该网页完全没用，因此当对一个网页有不同的评价的时候，选取对该网页评价高的用户的投票是较为合理的［8］。

2.2 改进的网页受欢迎度

首先以P(p,t)来度量网页的受欢迎度，即从时间t开始后的单位时间内网页p被访问的次数。以A(p,t)来度量用户熟知度，即在时间t时，用户对网页p的熟知度的比例。例如，到当前为止，有100，000个用户访问过网页p，且有10，000个用户熟知该网页，则该网页的用户熟知度A(p,t)就为0.1。需要注意的是，用户熟知度表示的是已经访问过该网页且能够确定是否喜欢该网页的用户数量，而网页受欢迎度表示的是用户知道该网页且喜欢该网页的数量。因此，在时间t时网页p受欢迎度为：

P(p,t)=A(p,t)•Q(p) (2)

一般令［8］

A(p,t)=1－e－rn∫t0P(p,t)dt(3)

如果知道网页p的当前受欢迎度，就可以估计出有多少用户已经访问了该网页。除去这部分用户之外，喜欢网页p的用户比例就是Q(p)，从而可以得出网页p受欢迎度的增长幅度。为此，本文给出下面改进的网页受欢迎度：

P(p,t)=Q(p)1+［Q(p)P(p,0)－1］e－［rnQ(p)］t (4)

其中P(p,0)是网页p在零时刻的受欢迎度，也就是在网页p第一次被创建时的受欢迎度。

对于公式(4)的成立情况证明如下：

由公式(2)和(3)可得

P(p,t)=［1－e－rn∫t0P(p,t)dt］Q(p) (5)

用f(p,t)替换e－rn∫t0P(p,t)dt，则P(p,t)与－nr(df(p,t)dt/f(p,t))相等，因此

(－nr)(1f(p,t))df(p,t)dt=

(1－f(p,t))Q(p) (6)

式(6)称为菲尔哈斯特等式。该等式的解为：

f(p,t)=11+CernQ(p)t (7)

其中C是一个常数用来确定边界条件。因f(p,t)=e－rn∫t0P(p,t)dt，所以

e－rn∫t0P(p,t)dt=11+CernQ(p)t (8)

在式(8)两边同时对t进行微分，可得

－rnP(p,t)=－rnQ(p)CernQ(p)t1+CernQ(p)t重新整理该式可得

P(p,t)=CQ(p)C+e－rnQ(p)t (9)

由等式(9)可以求得常量C，因为

P(p,0)=CQ(p)C+1 (10)

因此 C=P(p,0)Q(p)－P(p,0) (11)

将式(11)代入式(9)可得

P(p,t)=Q(p)1+［Q(p)P(p,0)－1］e－［rnQ(p)］t

因此，当t∞时，P(p,t)Q(p)，网页p的受欢迎度最终会趋近于Q(p)。

2.3 改进的网页真实质量评估函数

如果想精确地测定一个网页的质量，就需要大量真实用户访问该网页并从他们那里得到反馈。但这显然是不可能做到，因此需要在没有用户参与的情况下测定一个网页的质量，为此，论文给出下式来测定网页的估计质量：

Q(p,t)=dP(p,t)/dtP(p,t) (12)

其中P(p,t)为式(4)所定义的网页受欢迎度，dP(p,t)/dt表示网页p受欢迎度的增加量。

3 PROABIPD中网页质量评估函数

对公式(4)进行对时间求导后可以用来评估一个网页的质量，网页受欢迎度对时间的导数与网页质量关系如下：

Q(p)=(nr)dP(p,t)/dtP(p,t)(1－A(p,t)) (13)

以I(p,t)表示(nr)dP(p,t)/dtP(p,t)，称为相对受欢迎度增量函数，其与网页受欢迎度P(p,t)随时间变化的关系如图1所示。

从图1可以看出在一个网页刚被创建时，P(p,t)并没有很好的反映出该网页的质量，然而，访问该网页的用户大多数是第一次访问该网页，因此，如果该网页是一个高质量的网页，其受欢迎度会迅速增大，随着时间进行，越来越多的用户知道了该网页，其受欢迎度保持不变，且网页的质量Q(p)总是等于相对受欢迎度增量I(p,t)与其受欢迎度P(p,t)之和，即：Q(p)=I(p,t)+P(p,t)。

4 实 验

在以上讨论中，假设网页的质量是基于当前该网页的受欢迎程度以及对瞬时时间的导数，在实践中无法对瞬时时间进行有效测量，因此，只有在离散时间点对PageRank的增量进行估计：

Q*(p,ti)=nr［ΔPR(p,ti)/ΔtiPR(p,ti)］+PR(p,ti) (14)

其中PR(p,ti)是网页p在时间ti时刻的PageRank值，ΔPR(p,ti)=PR(p,ti)－PR(p,ti－1)且Δti=ti－ti－1。假设一个网页其初始质量Q为0.4，根据公式Q(t)=0.4+0.0006t在t=500时达到0.7，在每个时间间隔测量网页质量值，得出真实的质量、受欢迎度和估计质量值之间的关系，如图2所示。

从图2可得出如下结论：

1）评估器Q可以很好的测量网页的真实质量值；

2）Q*对最终的受欢迎度来说不是一个好的预测器，例如，在t=1时，Q*≈0.4，但在t=500时最终的受欢迎度是0.7，然而，应该注意到的是，对于网页p当前受欢迎度来说，Q对于最终的网页受欢迎度有更好的预测。

5 结束语

本文针对许多搜索引擎当前使用的PageRank算法易于出现 “富者更富” 的问题，提出了一种新的基于改进受欢迎度的PageRank优化算法，并与传统PageRank算法做了比较实验。实验结果表明该改进算法在一定程度上能够有效地解决“富者更富“的问题，从而为网页评估提供了一个更准确有效的方法。

参考文献

［1］ SerraCapizzano S.Jordan canonical from of the Google matrix: A potential contribution to the PageRank computation ［J］.SIAM J of MatrixAppL, 2005, 27(2):305-312.

［2］ Npd search and portal site study ［EB/OL］. (2008-9-23) ［2011-01-10］.www.省略/press/releases/press_000919.htm

［3］ 赵国,宋建成. Google搜索引擎的数学模型及其应用［J］ . 西南民族大学学报:自然科学版,2010,36(3): 480-486.

［4］ 潘昊,谭龙远. 领域相关自适应的PageRank算法搜索策略［J］.计算机应用,2008 ,28 (9): 2192-2194.

［5］ 丁岳伟,郭辉. 利用蚁群算法对PageRank算法的改进［J］. 计算机应用,2009 ,29 (10): 2726-2728.

［6］ BREZINSK C,ZAGLIA M R.SerraCapizzano S.Extrapolation methods for PageRank computations［J］.Les Comptes Rendus de l’Academic de Sciences de Paris Ser1,2005,340:393-397.

［7］ BAEZAYATES D, BOLDI P,CASTILLO C. Generalizing PageRank:Damping functions for link-based ranking algorithms［C］.//Proceedings of SIGIR, Selangor: Malaysia, 2006:308-315.

［8］ 杨劲松,凌培亮. 搜索引擎PageRank算法的改进［J］. 计算机工程,2009,35 (22): 35-37.省略)；刘俊辉（1980―），男，河南息县人，讲师，硕士，研究方向：计算机网络，数据库，计算机应用。