采用改進受歡迎度的PageRank優化算法
2011-01-01 00:00:00李娜劉俊輝
計算技術與自動化 2011年4期
文章編號：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)#8226;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 Matrix Anal AppL， 2005， 27(2):305-312.
［2］ Npd search and portal site study ［EB/OL］. (2008-9-23) ［2011-01-10］.http://www.npd.com/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.
收稿日期：2011-09-23
作者簡介：李 娜（1979—），女，河南鹿邑人，講師，碩士，研究方向：計算機數據庫，軟件工程 (E-mail：20887809@qq.com)；劉俊輝（1980—），男，河南息縣人，講師，碩士，研究方向：計算機網絡，數據庫，計算機應用。
