張書江

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院，安徽淮南232001)

摘要： 對搜索結(jié)果的排序是搜索引擎中至關(guān)重要的一項技術(shù)，算法的好壞直接關(guān)系到用戶輸 入關(guān)鍵詞后能不能迅速查看到要查找的信息。系統(tǒng)的介紹超鏈接分析技術(shù)及基于超鏈接分析 的搜索引擎頁面排序算法。對兩種最基本的頁面排序算法PageRank和HITS的算法思想和實現(xiàn) 原理進行詳細闡述。通過分析對比，總結(jié)出它們各自存在的優(yōu)點和不足進而指出適合其應(yīng)用 的條件領(lǐng)域。最后指出搜素引擎應(yīng)用超鏈接分析時應(yīng)注意的一些影響因素。

關(guān)鍵詞：搜索引擎；超鏈接分析；頁面排序；PageRank；HITS

中圖分類號：TP301文獻標識碼：A[WT]文章編號：16721098(2008)02007305

Analysis of Two Kinds of Search Engine Pageranking

Algorithm Based on Hyperlink Analysis

ZHANG Shujiang

(School of Computer Science and Engineering, Anhui University of Science and Tec hnology, Huainan Anhui 232001, China) Abstract: Search results sorting is a key technology in search engine, the algo rithmhas a direct influence on whether users can quickly find their expected i nformation afterkeywords are entered or not. The technology used for hyperlinkanalysis andpageranking algorithms based on hyperlink analysis were system ic ally presented. The ideas and principles of two of the most fundamental pager an king algorithms, PageRank and HITS, were expatiated. After analysis and comparis on, their respective advantages and disadvantages were summed up, and the condit ions and fields suitable for their application given. Finally some factors to benoted when search engine uses hyperlink analysis were pointed out.

Key words:search engine; hyperlink analysis; pageranking;PageRank; HITS

在互聯(lián)網(wǎng)發(fā)展初期，網(wǎng)站相對較少，信息查找也比較容易。然而伴隨互聯(lián)網(wǎng)爆炸性的發(fā)展， 從1994年萬維網(wǎng)（World Wide Web，WWW或Web）出現(xiàn)到現(xiàn)在短短十幾年的發(fā)展，由于其開放 性和其上信息廣泛的可訪問性極大的鼓舞了人們創(chuàng)作的積極性使其日益發(fā)展成為一個最為豐 富龐大的信息資源庫。對于一個普通互聯(lián)網(wǎng)用戶要想在這個碩大的信息庫中找到自己所需的 資料簡直如同大海撈針，這時為滿足大眾信息檢索需求的專業(yè)搜索網(wǎng)站便應(yīng)運而生了。

這些專業(yè)搜索網(wǎng)站的核心就是搜索引擎技術(shù)。而搜索引擎技術(shù)中搜索結(jié)果頁面的排序算法在 搜索引擎中處于舉足輕重的地位，因為排序算法決定了系統(tǒng)索引的網(wǎng)頁與用戶查詢意圖的相 關(guān)程度，同時也決定了網(wǎng)頁在查詢結(jié)果中出現(xiàn)的次序。它的好壞直接關(guān)系到用戶輸入關(guān)鍵詞 后能不能得到要查找的信息。因此搜索引擎頁面排序算法越來越受到眾多研究學(xué)者的青睞， 尤其是基于超鏈接分析的排序算法更是層出不窮。

1超鏈接分析技術(shù)簡介

傳統(tǒng)的Web搜索引擎大多數(shù)是基于關(guān)鍵字匹配的，返回的結(jié)果是包含查詢項的文檔。也有基 于目錄分類的搜索引擎，比如早期的Yahoo、新浪的搜索服務(wù)。但這些搜索引擎的搜索結(jié)果 并不令人滿意。因為有些網(wǎng)站擁有者為了使自己的網(wǎng)站在搜索結(jié)果中能排在較為前端的位置 故意提高某些關(guān)鍵字的出現(xiàn)頻率從而破壞了搜索結(jié)果的客觀性和準確性。此外，有些重要網(wǎng) 頁可能并沒有包含查詢項因而也就不可能被搜索引擎檢索到。

然而，一些研究學(xué)者們逐漸發(fā)現(xiàn)，Web上超鏈結(jié)構(gòu)是個非常豐富和重要的資源，如果能夠充 分利用的話，可以極大的提高檢索結(jié)果的質(zhì)量［1］189。進而提出了基于超鏈接分析 的搜索結(jié)果排序算法。文獻［2］78提出的PageRank算法開啟了超鏈接分析研究的熱 潮 。超鏈接分析的基本原理是：在某次搜索的所有結(jié)果中（大型商業(yè)搜索引擎通常會有數(shù)十萬 甚至上百萬個搜索結(jié)果），被其它網(wǎng)頁用超鏈指向越多的頁面，其價值就越高，在輸出排序 中就應(yīng)該排得越靠前［3］。即一個網(wǎng)頁的重要性取決于該網(wǎng)頁被其它網(wǎng)頁鏈接的數(shù) 量，特別是被一些已經(jīng)被認定為“重要”網(wǎng)頁鏈接的數(shù)量。

超鏈接分析其實是一種引用投票機制，也就說如果一個網(wǎng)頁被另外一個網(wǎng)頁鏈接一次就相當(dāng) 于另一網(wǎng)頁對其投了一票，其重要性被肯定一次。對于靜態(tài)網(wǎng)頁或網(wǎng)站主頁，這種機制具有 一定的合理性。因為這樣的網(wǎng)頁容易根據(jù)其在互聯(lián)網(wǎng)上受到的評價而產(chǎn)生超鏈接指向的數(shù)量 ，超鏈分析的結(jié)果可以從很大程度上反映該網(wǎng)頁的實際重要程度，能夠為搜索用戶返回接近 其搜索意圖且很有價值的搜索結(jié)果。事實上，超鏈分析技術(shù)除了分析網(wǎng)頁本身的文字外，還 分析所有指向該網(wǎng)頁的鏈接URL、鏈接文字、甚至鏈接周圍的文字。這樣，有時候即使某個 網(wǎng)頁html1中并沒有包含某個詞，比如“下載”，但如果有別的網(wǎng)頁html2用鏈接文字“下載 ”指向這個網(wǎng)頁html1，那么用戶在搜索“下載”這個關(guān)鍵詞時也能找到網(wǎng)頁html1。而且， 如果有越多網(wǎng)頁（html2、html3、html4、html5…）用“下載”鏈接指向這個網(wǎng)頁html1 ，或者給出這個鏈接的源網(wǎng)頁（html2、html3、html4、html5…）越優(yōu)秀，那么網(wǎng)頁html 1在用戶搜索“下載”時就會被認為越相關(guān)，在搜索結(jié)果中的排名也就會越靠前。

由此看見，所謂鏈接分析主要基于如下兩個重要假設(shè):①超文本鏈接包含了用戶對一個網(wǎng)站 的判斷信息;②對一個網(wǎng)站而言，如果其他網(wǎng)站鏈接到該網(wǎng)站的鏈接數(shù)（即入鏈數(shù)）越多， 則該網(wǎng)站越重要。這兩個假設(shè)在各種基于鏈接分析的算法中均以某種方式體現(xiàn)出來［2 ］78。

基于這種超鏈分析思想，一些學(xué)者提出了許多頁面排序算法。目前有：PageRank算法、HITS算法、SALSA（Stochastic Approach for LinkStructure Analysis）算法、PHITS算法（Probabilistic analogue of the HITS）；貝葉斯算法、Reputation算法［3］6。還有在各自的基礎(chǔ)上進行改進而產(chǎn)生的算法變種。這些算法 有的已經(jīng)在實際的系統(tǒng)中實現(xiàn)和使用，并且取得了良好的效果。在這些算法中，PageRank和 HITS是最著名也是最基本的頁面排序算法，其它算法是在兩者基礎(chǔ)之上進行某種程度的改進 版。下面對這兩個基本算法作個詳細的介紹與分析以為以后的研究工作做好基礎(chǔ)準備工作。

2基于超鏈接分析的算法

2．1PageRank算法

2.1.1基本思想在基于超鏈接分析的排序算法中，PageRank算法是最有名的一種。它最初是Sergey Brin和L awrence Page在1998年提出的，后來被用在世界上最著名的搜索引擎Google中一直到今天。 Google通過PageRank元算法計算出網(wǎng)頁的PageRank值，從而決定網(wǎng)頁在搜索結(jié)果集中的出現(xiàn) 位置，PageRank值越高的網(wǎng)頁，在結(jié)果中出現(xiàn)的位置越靠前。

其基本思想是:如果某一網(wǎng)頁玊存在一個指向網(wǎng)頁A的鏈接，則表明網(wǎng)頁T的所有者認為網(wǎng)頁 A是比較重要的，從而把T重要性得分值（即網(wǎng)頁T的PageRank值）的一部分賦予獳。A 得到的分值大小由玊的PageRank值玃R(T)和T的出鏈(從T鏈出的鏈接)數(shù)C(T)決定。用公 式表示為:PR(T)/C(T)。因而對于頁面A，其PageRank值玃R(A)就是從所有指向它的頁 面分得的重要性分值的總和?？捎靡韵鹿接嬎悭狿R(A)=PR(T1)/C(T1)+…+

PR(Tn)/C(Tn)(1)

其中：玊1、T2、T3…Tn為含有指向A的鏈接的頁面。

由于互聯(lián)網(wǎng)上也存在一些頁面沒有入鏈或出鏈那么就無法計算其PageRank值。為避免這個問 題（即所謂的LinkSink問題）一些研究學(xué)者對其進行改進，為式（1）添加一個阻尼系數(shù) 玠使其變?yōu)?/p>

PR(A)=(1-d)+d［PR(T1)/C(T1)+…+PR(Tn)/C(Tn)］(2)

玠為阻尼系數(shù)，Google常指定為0.85［4］。這樣在整個網(wǎng)絡(luò)內(nèi)的頁面經(jīng)過多次遞 歸迭代計算，直到PR值達到收斂即求得頁面的PageRank值。

2.1.2優(yōu)缺點分析從以上PageRank的計算公式中也以看出，一個頁面會將自己的PageRank值均勻的分配給它所 引用的頁面，它引用的頁面越多，每個被它引用的頁面所分得的PageRank值越少。因而一個 頁面會因為別的頁面對自己的引用而增加自己的PageRank值，但并不會因為自己對別的頁面 的引用而提高自己的PageRank值。這樣，對于一個網(wǎng)頁來說要想獲得較為靠前的排名就要獲 得較大的PageRank值，而要獲得較大的PageRank值就要被較多重要的網(wǎng)站所引用，因為只有 那些重要網(wǎng)站才有較大的PageRank值。而如果兩個頁面各自本身的PageRank值都很低，則它 們互相鏈接后也增加不多，重復(fù)鏈接對兩者更是有害無益。由于頁面的鏈接數(shù)越多，被鏈接 頁面得到的PageRank值就會越低因此高級別的網(wǎng)站也不會與質(zhì)量不高的網(wǎng)站互換鏈接。一個 網(wǎng)站要想獲得較高級別的PageRank值就只有一個辦法那就是要求網(wǎng)站擁有者老老實實地做好 自己的每一個網(wǎng)頁，提高整個網(wǎng)站的質(zhì)量水平才能換得高級別網(wǎng)站的鏈接。所以PageRank技 術(shù)可以很有效的避免某些網(wǎng)站為獲得較高排名來欺騙搜索引擎。

PageRank技術(shù)的另外一個優(yōu)點在于它是一個與查詢無關(guān)的靜態(tài)算法。盡管所有網(wǎng)頁的PageRa nk值都要通過進行遞歸迭代計算以求得收斂值，這一過程中計算量很大，但這些計算不要求 實時性，可以離線計算獲得結(jié)果后保存起來。這樣能有效的減少在線查詢時的運算量極大的 縮短查詢響應(yīng)時間。

然而，PageRank技術(shù)的缺點也是顯而易見的。因為PageRank僅僅依靠計算網(wǎng)頁的外部鏈接數(shù) 量來決定該網(wǎng)頁的排名，而完全忽略了頁面的主題內(nèi)容與用戶查詢意圖的相關(guān)性從而影響搜 索結(jié)果的相關(guān)性和準確性。另外，有一些Hub頁本身并不突出，除了鏈接外也沒有多少內(nèi)容 也沒有多少鏈接指向它，但它卻指向了某個話題最突出的頁面鏈接。可以說一個好的頁面由 多個好的Hub頁面所指向，一個好的Hub頁面指向多個好的頁面。這應(yīng)該是一種互動關(guān)系，但 在PageRank中并沒有考慮到［5］。再者，對于一些較新的網(wǎng)頁由于還沒有被發(fā)現(xiàn)故 被引用的次數(shù)很少因而即使質(zhì)量很高也不會獲得很高的PageRank值。也就是說PageRank會對 新網(wǎng)頁表現(xiàn)很大的歧視性。

2．2HITS算法

2.2.1基本思想HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超鏈 接分析排序算法中另一個最著名的算法之一。在該算法中,按照超鏈接的方向,將網(wǎng)頁分成兩 種類型的頁面：Authority頁面（權(quán)威頁）和Hub頁面（目錄頁）。二者是HITS算法中兩個十 分重要的概念。Authority頁面是指與某個查詢關(guān)鍵詞和組合最相近的頁面；Hub頁面是指它 的出鏈中包含了很多的Authority頁面的頁面，它的主要功能就是把這些Authority頁面聯(lián)合 在一起［6］。

HITS基本思想是：將查詢玵提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引擎，搜索引擎返回很 多網(wǎng)頁，從中取前玭個網(wǎng)頁作為根集(Root Set)，用玆表示。R一般滿足如下三個條件 ：① R中網(wǎng)頁數(shù)量相對較??；② R中網(wǎng)頁大多數(shù)是與查詢q相關(guān)的網(wǎng)頁；③ R中包 含 較多的權(quán)威網(wǎng)頁。然后根據(jù)這個集合R在整個網(wǎng)頁有向圖中的位置來擴展這個根集合。即通 過向R加入被R引用的網(wǎng)頁和引用R的網(wǎng)頁將R擴展成一個更大的集合稱為基集T。在得到這 個集合后，就開始計算集合中每個網(wǎng)頁的目錄型權(quán)值和權(quán)威型權(quán)值。利用Authority頁面和H ub頁面互相增強屬性,對集合玊進行鏈接分析,通過迭代的計算方法為玊中的每個頁面 計算一個Authority值和一個Hub值,作為結(jié)果頁面排名的依據(jù)。

假定基集玊中的頁面分別為 1，2，3，…玴 。每個頁面玴有一個Authority值玜 p和Hub值玥p；頁面玴的入鏈頁面集表示為Bp(m），出鏈頁面集表示為獸p（n ）。則ap和hp用如下公式進行計算

ap=∑[DD(]m[]i=1[DD)]hi(i∈Bp(m))

hp=∑[DD(]n[]i=1[DD)]ai(i∈Fp(n))

這樣的遞歸式很容易用矩陣方法表示。令所有選出來的網(wǎng)頁都進行標號，得到所有網(wǎng)頁的編 號集｛1,2,…,玭｝。令相鄰矩陣A為一個n×n的矩陣，如果存在一個從 網(wǎng)頁i 鏈接到網(wǎng)頁j 的超鏈，就令矩陣中A的第（i, j）個元素置為1，否 則置為0。同時，將所有網(wǎng)頁的權(quán)威型 權(quán)值x和目錄型權(quán)值y都分別表示成向量x=(x1,x2,x3,…,xn),y=(y1,y2,y3, …,yn)。由此可以得到計算x和y的簡單矩陣公式：y=A?x,x=A 琓?y其中A琓是A的轉(zhuǎn)置矩陣。進一 步，我們有：

x=A琓?y=A琓?Ax=( A琓A)?x

y=A琓?x=AA琓y=(AA琓)? y

因此向量玿,y均可經(jīng)過多次迭代而得。經(jīng)過一定次數(shù)的遞歸運算后，會得到集合中每個網(wǎng) 頁的權(quán)威型權(quán)值和目錄型權(quán)值。按照這兩個不同的權(quán)值，分別取出前k個頁面輸出返回給 用戶。根據(jù)線性代數(shù)的理論,迭代序列經(jīng)過標準化最終將收斂于矩陣A的 特征向量,即上文計 算的Hub權(quán)值和Authority權(quán)值是頁面集合的固有特征,不是由初始向量和參數(shù)的選擇決定的 。

2.2.2優(yōu)缺點分析由HITS的計算過程我們可以看出這種算法是一種依賴于查詢關(guān)鍵字的算法。每得到一個檢索 ，它都要從數(shù)據(jù)庫中找到相應(yīng)的網(wǎng)頁，同時提取出這些網(wǎng)頁和鏈接構(gòu)成的有向子圖，再通過 運算獲得各個網(wǎng)頁的相應(yīng)鏈接權(quán)值。實際應(yīng)用中，由R生成T的時間開銷是很昂貴的 ，需要下 載和分析R中每個網(wǎng)頁包含的所有鏈接，并且排除重復(fù)的鏈接。一般玊比R大很 多，由T生 成有向圖也很耗時。需要分別計算網(wǎng)頁的A/H值，計算量比PageRan k算法大。已有實驗數(shù)據(jù) 表明，這種算法獲得的排名準確性高于PageRank算法。但在用戶檢索時進行如此大量的運算 ，檢索效率顯然不高。

HITS算法最大的弱點是處理不好主題漂移問題（topic drift），也就是緊密鏈接TKC（Tigh tlyKnit Community Effect）現(xiàn)象［7］。由于HITS只計算主特征向量，也就是只 能發(fā)現(xiàn)玊集合中的主社區(qū)（Community），忽略了其它重要的社區(qū)。如果在集合玊中 有少數(shù)與查詢主題無關(guān)的網(wǎng)頁，但是他們是緊密鏈接的，HITS算法的結(jié)果可能就是這些網(wǎng)頁 ，從而偏離了原來的查詢主題。因此，HITS更適合于寬主題的查詢。

另外，HITS算法不能有效的識別網(wǎng)站制作者對搜索引擎的欺騙。Web頁面中有許多鏈接是為 其他目的而創(chuàng)建的,例如付費廣告、網(wǎng)站本身導(dǎo)航等等,因此單憑鏈接數(shù)目來判斷頁面的Auth ority值和Hub值,是不合理的。

用HITS進行窄主題查詢時，還可能產(chǎn)生主題泛化問題，即由根集到基集的擴展后引人了比原 來主題更重要的新主題，新主題可能與原始查詢無關(guān)。泛化的原因是因為網(wǎng)頁中包含不同主 題的向外鏈接，而且新主題的鏈接更加具有重要性。

3超鏈接分析應(yīng)注意的問題

基于超鏈接分析的算法，提供了一種衡量網(wǎng)頁質(zhì)量的客觀方法，獨立于語言，獨立于內(nèi)容， 不需人工干預(yù)就能自動發(fā)現(xiàn)Web上重要的資源，挖掘出Web上重要的社區(qū)，自動實現(xiàn)文檔分類 ［3］4。但由于互聯(lián)網(wǎng)的開放性和自由性使得Web頁面上的超鏈接也呈現(xiàn)魚龍混雜狀 態(tài)，給超鏈分析工作帶來一定的干擾和欺騙。避害趨利，力求算法做到最大程度的精確 有效。有一些共同的問題影響著算法的精度我們必須給與重視。

(1) 根集的質(zhì)量根集質(zhì)量應(yīng)該是很高的，否則，擴展后的網(wǎng)頁集會增加很多無關(guān)的網(wǎng)頁， 產(chǎn)生主題漂移，主題泛化等一系列的問題，計算量也增加很多。算法再好，也無法在低質(zhì)量 網(wǎng)頁集找出很多高質(zhì)量的網(wǎng)頁。

(2) 噪音鏈接Wed上不是每個鏈接都包含了有用的信息，比如廣告，站點導(dǎo)航，贊助商， 用于友情交換的鏈接，對于鏈接分析不僅沒有幫助，而且還影響結(jié)果［1］196。如何 有效的去除這些無關(guān)鏈接，也是算法的一個關(guān)鍵點。

(3) 錨文本的利用錨文本有很高的精度，對鏈接和目標網(wǎng)頁的描述比較精確。在具體的實 現(xiàn)中我們應(yīng)大加利用錨文本來優(yōu)化算法。如何準確充分的利用錨文本，對算法的精度影響很 大。

(4) 查詢的分類每種算法都有自身的適用情況，對于不同的查詢，應(yīng)該采用不同的算法， 以求獲得最好的結(jié)果。因此，對于查詢的分類也顯得非常重要。

4結(jié)束語

隨著Internet上信息量的爆炸式增長，人們越來越依賴于搜索引擎獲取所需信息。雖然目前 的商用搜索引擎取得了很大的成功，但還有許多方便需要進一步完善。本文主要對基于超鏈 接分析的兩種最基本的搜索結(jié)果排序算法PageRank和HITS進行了詳細介紹和分析對比。希望 為將來在這兩種算法思想的基礎(chǔ)上進行改進，提出更精確更完善的排序算法打下基礎(chǔ)。搜索 引擎的研究是一個熱點,要能真正的研究并有所創(chuàng)新,對現(xiàn)有基礎(chǔ)技術(shù)理論的學(xué)習(xí)和深入理解 是基礎(chǔ)。

參考文獻：

［1］李曉明，閆宏飛，王繼民.搜索引擎——原理、技術(shù)與系統(tǒng)［M］.北京：科 學(xué)出版社,2004：189，196.

［2］吳江.使用超鏈分析技術(shù)的搜索引擎［J］.圖書情報工作，2004，48(7)：78 81.

［3］李紹華，高文宇.搜索引擎頁面排序算法研究綜述［J］. 計算機應(yīng)用研究，2007,24(6):47.

［4］劉琨，鄭有才.搜索引擎剖析［J］.微機發(fā)展，2004,14(3):1922.

［5］徐寶文,張衛(wèi)豐.搜索引擎與信息獲取技術(shù)［M］. 北京:清華大學(xué)出版社,200 3：109110.

［6］張娜，張化祥.基于超鏈接和內(nèi)容相關(guān)度的檢索算法［J］. 計算機應(yīng)用，2 006,26(5):1 1711 173.

［7］鄭煜,錢榕.一個基于鏈接分析的相關(guān)度排序算法及其在專題搜索引擎中應(yīng)用 ［J］.計算機應(yīng)用與軟件，2007，24（7）：5455.

(責(zé)任編輯：李麗)