基于PageRank與HITS的改進算法的網頁排名優化

庫 珊，劉 釗

(1. 武漢科技大學計算機科學與技術學院，湖北 武漢，430065；2. 武漢科技大學智能信息處理與實時工業系統湖北省重點實驗室，湖北 武漢，430065)

PageRank算法是1998年由Google創始人Sergey Brin和Lawrence Page提出的基于鏈接分析的網頁排序算法[1]，其思想是通過分析網絡的鏈接結構來獲得網絡中網頁的重要性排名。傳統的PageRank算法中，對于同一網頁鏈出時的頁面等級值(PageRank)是同等對待且平均分配的，沒有考慮到不同鏈接的重要性會有所不同，而這與Web鏈接的實際情況不符。幾乎在同一時期，康奈爾大學的Kleinberg博士提出了HITS算法[2]，作為同樣基于鏈接分析的算法，該算法中引入了樞紐(Hub)頁面和權威(Authority)頁面的概念，兩者的相互優化關系構成了HITS算法的基礎，但是兩者在迭代過程中會相互增強，對查詢結果的準確性造成影響。此后，相繼出現了ARC[3]、SALSA[4]算法等一系列以鏈接分析為基礎的頁面分級算法，并且在實際應用中取得了一定的成果。另一方面，為解決傳統PageRank和HITS算法中存在的不足，國內外研究者也提出了許多改進算法，如文獻[5]提出了結合鏈接和內容信息的改進PageRank算法，其去除了PageRank算法需要的前提，考慮到了用戶從一個網頁直接跳轉到非直接相鄰但內容相關的另外一個網頁的情況。文獻[6]提出了通過在PageRank算法中添加鏈入鏈出權重因子、用戶反饋因子、主題相關因子和時間因子，使得搜索結果更接近用戶查詢需求，同時兼顧了搜索內容的相關度和查準率。文獻[7]提出利用PageRank算法對Lucene原有的排序算法進行改進，設計并實現了一個針對移動信息的個性化搜索引擎。文獻[8]提出了一種結合網頁文本分析和擴散速率改進的F-HITS算法，以解決傳統HITS算法中易發生主題漂移、計算效率低等問題。

基于此，本文通過分析傳統PageRank和HITS算法中存在的不足，提出了一種基于這兩種算法的改進算法PHIA(PageRank and HITS Improved Algorithm)，該算法繼承了HITS算法獲取根集和基本集的方法，并使用根集中所有網頁的PageRank值作為Hub值和Authority值的初始迭代值，放棄了HITS算法中的相互迭代方式，而是通過求馬爾可夫矩陣的方式來獲取網頁排名的靜態分布。

1 網頁排序算法

1.1 PageRank算法

PageRank算法是根據網頁超鏈接之間的相互關系來確定網頁的重要性和排名的，基于“由許多網頁或一些權威網頁鏈接的網頁必然是權威網頁”的前提條件，以網頁間的鏈接結構為基礎，來劃分網頁的重要性等級[9]。在鏈接網絡中，將網頁A指向網頁B的鏈接看作是A對B的投票，根據一個網頁所獲得的投票次數來判斷網頁的重要性，一個網頁的PageRank值PR可由下式(1)表示：

(1)

式中：i、j表示網頁；Q(i)表示網頁i指向的鏈接集合；S(j)表示網頁j指向的所有鏈接的數目；PR(j)表示頁面集Q(i)中任意一個頁面j的PR值；PR(j)/S(j)則表示網頁i的鏈入網頁j給予網頁i的PR值。

但在實際應用中，Web連接圖中常常存在一些出度或入度為0的節點，即存在環的情況,這時會出現兩種異常：等級泄露(Rank Leak)和等級下沉(Rank Sink)[10]。為避免上述現象，可以在去掉Web鏈接中所有出度為0的節點后，定義一個阻尼系數d(0

(2)

式中：m表示節點的總個數。

一個頁面的PageRank值是由所有鏈向它的頁面(鏈入頁面)的重要性經過遞歸算法得到的，計算過程需要迭代。大量實驗證明，經過反復迭代計算得到網頁的PageRank值是收斂且有效的。PageRank 算法作為與查詢主題無關的靜態算法，所有網頁的PageRank 值均可以通過后臺離線計算獲得，這有效地減少了在線查詢時的計算量，降低了用戶查詢相應的時間。然而，PageRank算法的特點使其仍受制于主題漂移、偏重舊網頁、忽視用戶個性化等問題。

1.2 HITS算法

HITS算法是一種基于超鏈接分析的網頁排序算法。該算法中，網頁被分為Authority和Hub兩種類型，所謂Authority頁面指的是與查詢主題最為相關并具有高質量、權威性的網頁，Hub頁面則是指提供指向Authority網頁鏈接集合的網頁。同時，也為每個網頁定義了兩個權值，即Authority值和Hub值，用來判斷該網頁對特定主題的重要性。

HITS算法的建立基于以下兩點假設：①一個好的Authority頁面會被很多好的Hub頁面指向；②一個好的Hub頁面會指向很多好的Authority頁面。該算法的具體實現過程為：

Step1將查詢主題q提交給某搜索引擎，從返回結果頁面的集合中取前n個結果作為根集Q，Q需要滿足：①Q中網頁數量足夠小；②Q中包含很多與查詢相關的頁面；③Q中包含很多高質量的Authority頁面。

Step2通過向Q中加入被Q引用的網頁和引用Q的網頁，將其擴展成一個更大的集合T。以T中的Hub 網頁為頂點集V1，以Authority網頁為頂點集V2，以V1到V2的超鏈接為邊集E，形成一個二分有向圖G=(V1，V2，E)。對于V1中任一頂點v，用h(v)表示其Hub值；對于V2中任一頂點u，用a(u)表示其Authority值。

Step3初始化a、h，令a0=h0= 1。

Step4分別對u、v進行如下操作，以修改a(u)和h(v)的值：

①a(u)=∑h(v)；②h(v)=∑a(u)。

Step5對a(u)、h(v)進行規范化處理，即：

Step6不斷地重復Step4和Step5，直至a(u)、h(v)收斂，輸出最大的Authority值和Hub值。

與PageRank算法不同，HITS算法與用戶輸入的查詢請求密切相關，因而必須在接收到用戶查詢后進行實時計算，計算效率較低；另一方面，盡管HITS算法在某些查詢主題下能夠較為準確地提取出Authority網頁，但若擴展網頁集合里包含部分與查詢主題無關的頁面，且這些頁面之間有較多的相互鏈接指向，那么使用HITS算法很可能會給予這些無關網頁很高的排名，導致搜索結果發生“主題漂移”。此外，HITS算法還存在易被作弊者操縱結果、結構不穩定等問題。

2 基于PageRank和HITS的改進算法PHIA

針對上述不足，本文提出了一種基于PageRank和HITS算法的改進算法PHIA。該算法繼承了HITS算法獲取根集和基本集的方法，并且使用根集中所有網頁的PageRank值作為Hub值和Authority值的初始迭代值，以避免“主題漂移”現象的發生；其次，改進算法放棄了HITS算法中的Hub值和Authority值相互迭代方式，而是通過求馬爾可夫矩陣及其特征向量的方式來獲取網頁排名的靜態分布，以避免其相互迭代所產生的增強值誤差。算法PHIA的具體實現步驟為：

Step1根據用戶請求，用Google、Firefox等常用搜索引擎進行查詢，取返回頁面中的前n個網頁作為算法的根集，記為Q。隨后對集合Q進行擴充，方法為將根集Q中每一節點的入鏈(所有指向該節點的頁面)和出鏈(該節點指向的所有網頁)補充進來，形成基本集，記為SQ。

Step2求SQ中頁面的PageRank值。設W為SQ中頁面的集合，N=|W|，Ri為頁面i指向的所有頁面的集合，Bi為指向i的所有頁面的集合；對每個出度為0或出度頁面不在SQ中的頁面s，設RS={SQ中所有頁面的集合}，則所有其他節點的Bi={Bi∪s}，這樣可以將結點s所具有的PageRank值均勻地傳遞給其他所有頁面i。由此，頁面i的PageRank值PR(i)可以通過以下兩步計算得出：①以概率“1—m”隨機取基本集SQ中任意頁面i；②以概率m隨機取指向當前頁面i的頁面j，如果j?SQ，則重新選擇頁面j。PageRank算法的具體迭代公式為：

(3)

式中：參數m為取值范圍在0～1范圍的衰減因子，通常被置為0.85。

Step3用計算得到的PageRank值代替SQ集中每一個頁面的Authority和Hub初始值。從集合SQ構造無向圖G′ = (Vh,Va,E)，得到兩條鏈，即Authority鏈和Hub鏈：

Vh=(sh|s∈SQ∪出度(s)>0}

(G′的Hub邊)

Va={sa|s∈SQ∪入度(s)>0}

(G′的Authority邊)

E={(sh,ra)}s→rinSQ}

Step4根據2條馬爾可夫鏈[11]定義其變化矩陣，也即隨機矩陣，分別是Hub矩陣H和Authority矩陣A。

(4)

(5)

Step5求出矩陣H、A的主特征向量，即為對應的馬爾可夫鏈的靜態分布，H、A中較大數值所對應的網頁為所查找的重要網頁。

3 實驗結果及驗證

為驗證改進PHIA算法的正確性和有效性，本文建立了一個實驗系統，即用網絡爬蟲工具Heritrix在Google搜索引擎上，采用BroadScope模式對新浪微博網站的“娛樂版塊”和“研究版塊”進行網頁抓取。這兩個板塊中，各節點之間具有良好的互動關系，因此能夠較好地模擬互聯網的網絡結構。本文隨機選取“趙麗穎”和“Web前端”作為查詢主題，由于本實驗選擇的新浪微博中兩個板塊的網頁是由人工分類所形成的，并且所查詢關鍵字的含義較為簡單，故根據改進算法得到的每個網頁的Hub值和Authority值是可以信賴的。

從以“趙麗穎”為主題查詢得到的頁面中選取前8 個頁面，分別用A～H表示，各頁面之間的鏈接關系如圖1所示。利用PageRank、HITS及改進PHIA算法計算各網頁的權值，結果列于表1～表3中。從表1和表2中可以看出，所選擇的

圖1 以“趙麗穎”為搜索主題的頁面鏈接關系

Fig.1Pagelinkrelationshipwith“ZhaoLiying”asthesearchtopic

表1 以“趙麗穎”為搜索主題的基于PageRank算法的計算結果(迭代次數：15次)

表2 以“趙麗穎”為搜索主題的基于HITS算法的計算結果(迭代次數：20次)

表3 以“趙麗穎”為搜索主題的基于PHIA算法的計算結果(迭代次數：10次)

8個網頁中，PageRank值最高的頁面是H頁面，其次為F頁面和G頁面；最好的Authority頁面為F頁面和E頁面，最好的Hub頁面為D頁面，其次為E頁面和G頁面，同時有較高的Authority權值和Hub權值的頁面為E頁面、G頁面和H頁面。由表3所示改進PHIA算法的計算結果可知，具有高Authority值的頁面為H頁面、F頁面和B頁面，有高Hub值的頁面為E頁面、D頁面和H頁面，同時具有高Authority值和Hub值的頁面為H頁面、E頁面和G頁面。

以“Web前端”為搜索主題進行查詢，從返回結果網頁中選取8個頁面，分別標號為1～8，其鏈接關系如圖2所示，3種算法計算得到各網頁的權值列于表4中。由表4可見，利用PageRank算法計算得到排序第一的是頁面4，其次為頁面1

和網頁7；HITS算法下，最好的Hub網頁為頁面8，次為頁面5和頁面6，最好的Authority頁面為頁面4，其次為頁面2；而改進PHIA算法下，計算得到Hub值較高的頁面依次為頁面5、頁面8和頁面1，Authority值較高的頁面依次為頁面4和頁面2。

圖2 以“Web前端”為搜索主題的頁面鏈接關系

Fig.2Pagelinkrelationshipwith“Webfront-end”asthesearchtopic

根據上述實驗結果可知，基于PageRank和HITS的改進算法PHIA能夠更全面地找出所查詢關鍵詞的重要頁面；更重要的是，PHIA算法所需要的迭代次數為10次，少于PageRank算法(15次)和HITS算法(20次)所需的迭代次數，計算量大大減少；根據對查詢結果進行分析可知，頁面H和頁面E在內容上與搜索主題“趙麗穎”關聯密切，頁面4的內容與“Web前端”的關聯度也相對較高。另外，當限制最大迭代次數時，若迭代次數較少，PageRank算法得到的高PR值頁面是隨機出現的，即可能是8個頁面中的任一頁面；HITS算法一直指向的是同一個頁面，與迭代次數無關；PHIA算法則能夠找到最好的Authority頁面和Hub頁面。可見，PHIA算法的精度要高于PageRank和HITS算法，不足之處是當迭代次數足夠多時，HITS算法和PHIA算法精確度相差不大。

4 結語

本文通過分析經典的基于鏈接分析排序算法PageRank和HITS中存在的不足，提出了一種改進算法PHIA。該算法繼承了HITS算法獲取根集和基本集的方式，并利用根集中各網頁的PageRank值作為Hub值和Authority值的初始迭代值，在一定程度上避免了“主題漂移”現象的發生；另外，PHIA算法放棄了HITS算法中Hub值和Authority值相互迭代的方式，而是通過求馬爾可夫矩陣來獲取網頁排名的靜態分布，以解決兩權值相互迭代過程中產生的增強值誤差。從針對兩個隨機關鍵詞的檢索結果來看，PHIA算法雖然在一定程度上削弱了主題漂移和Hub值和Authority值相互迭代導致的增強效果，并且收斂速度也有了一定的提高，但是PHIA算法仍然存在一些缺陷，有待進一步改進：① PHIA算法只是在一定程度上削弱了“主題漂移”現象的產生，并不能完全避免；② 目前本系統只在本機中實驗，未考慮到人機交互、并發等問題，故還需在實際應用中加以完善。