搜索引擎中的ｗｅｂ鏈接算法研究與改進

摘要:該文就搜索引擎中鏈接結構算法問題進行研究，分析了PageRank和HITS兩種不同的算法，并對算法中明顯的缺陷提出了改進措施。通過測試，驗證使用改進的算法在搜索質量等方面有明顯提高。

關鍵詞:搜索引擎;web鏈接;PageRank;HITS

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)24-6748-02

Research and Improvement of the Web-link Algorithms in Search Engine

WANG Mei

(Jiangsu Maritime Institute， Nanjing211170， China)

Abstract: This article researches algorithms of search engine link structure， analyzes HITS PageRank and the algorithms of apparent defect. Improving measures are put forward. Through the test， the test in the search algorithm improves the quality， etc.

Key words: search engine; web-link; PageRank; HITS

隨著互聯網的迅猛發展，Web上信息量呈爆炸式增長，網上的資源及其豐富，但同時也充斥著大量的垃圾信息。 人們依據搜索引擎中的關鍵詞進行鏈接時，迫切需要從紛繁蕪雜的信息中找到有用知識，因此，通過有效的鏈接算法判斷網頁十分重要。

目前Google、百度等的鏈接算法使用PageRank算法和HITS算法。PageRank算法的特點在于對網頁進行了基于權威值的排序處理，最重要的網頁出現在結果的最前面。HITS算法是在描述網頁與主題的相關度時引入了權威網頁(Authority)和中心頁面(Hub)的概念，反映了權威網頁和中心網頁的相互加強關系。

1PageRank算法和HITS算法

1.1 PageRank算法

PageRank算法是將鏈接的網頁基于權威值按序排列。網頁的權威值基于下列考慮:1)一個網頁被多次引用，或者雖然沒有被多次引用，但是被重要的網頁引用，則它可能是很重要的。這種重要的網頁稱為權威(Authoritive)網頁。2)假定用戶一開始隨機地訪問網頁集合中的一個網頁，以后跟隨網頁的向外鏈接向前瀏覽網頁，不回退瀏覽，瀏覽下一個網頁的概率就是被瀏覽網頁的PageRank值。

PageRank算法描述如下:A(u)是網頁u的網頁集合，N(v)是網頁v指向外的鏈接數，v∈A(u)，c是一個用于規范化的因子(Google通常取0.85)，則u的PageRank值R(u)計算如下:

R(u)=cΣA(u)/N(v)(1)

但是如果有2個相互指向的網頁a，b，他們不指向其它任何網頁，另外有某個網頁c，指向a，b中的某一個，比如a，那么在計算中，a，b的PageRank值就無法分布而不斷地累計。解決這個問題的辦法可以在算法中引入衰退因子E(u)，因此式(1)改進如下:

R’(u)= cΣA(u)/N(v)+cE(u)(2)

1.2 HITS算法

HITS的算法主要考慮權威網頁(Authority)和中心網頁(Hub)之間的加強關系。每個網頁都會有一個對應的權威值和中心值，如果某個網頁有許多中心值高的網頁指向它，則它就有高的權威值;同樣，如果某個網頁指向了許多高權威的網頁，那么它將具有較高的中心值。

它的算法描述為:將查詢q提交給基于關鍵字匹配的搜索引擎.搜索引擎返回很多網頁，從中取前n個網頁作為根集(root set)，用S表示。S滿足如下3個條件:

1)S中網頁數量相對較小。2)S中網頁大多數是與查詢q相關的網頁。3)S中網頁包含較多的權威網頁

通過向S中加入被S引用的網頁和引用S的網頁將S擴展成一個更大的集合T，稱為基礎集。以T中的Hub網頁為頂點集V，以權威網頁為頂點集U，V中的網頁到U中的網頁的超鏈接為邊集E，形成一個二分有向圖SG=(V，U，E)。對V中的任一頂點v，用h(v)表示網頁v的Hub值;對U中的頂點u，用a(u)表示網頁的Authority值。開始時h(v)=a(u)=1，對u執行下列(3)式操作修改它的a(u)，對v執行下列式(4)操作修改它的h(v)，如此不斷地重復計算直到a(u)，h(v)收斂。

a(u)=∑h(v) (3)

h(v)=∑a(u) (4)

(3)式反映了若一個網頁由很多好的Hub指向，則其權威值會相應增加(即權威值增加為所有指向它的網頁的現有Hub值之和)。式(4)反映了若一個網頁指向許多好的權威頁，則Hub值也會相應增加(即Hub值增加為該網頁鏈接的所有網頁的權威值之和)。

2 算法存在的問題和改進措施

2.1 PageRank和HITS算法存在的問題

PageRank算法只返回包含查詢項的網頁，然后根據網頁的PageRank值對搜索到的結果進行排序。它把PageRank值最高的網頁放置到最前面，但是如果最重要的網頁不在結果網頁集中，PageRank算法就無能為力了;另外，用戶在網頁瀏覽時，回退瀏覽較多。

同樣，HITS算法也存在問題，比如:1)有些網頁在制作時，加入了一些與查詢主題無關的鏈接;比如商業廣告，贊助商和用于友情交換的鏈接，這些都降低了HITS算法的精度。2)有時，主機A上的很多文檔可能指向另外一臺主機B上的某個文檔，這就增加了A上文檔的Hub值和B上文檔的Authority，相反的情況也如此。3)HITS算法最大的弱點是處理不好主題漂移問題(topic drift)，也就是緊密鏈接TKC(Tightly-Knit Community Effect)現象。如果在集合T中有少數與查詢主題無關的網頁，但是他們是緊密鏈接的，HITS算法的結果可能就是這些網頁，偏離了原來的查詢主題。4)用HITS進行窄主題查詢時，可能產生主題泛化問題，即擴展以后引入了比原來主題更重要的新的主題，新的主題可能與原始查詢無關。

2.2 改進PageRank算法

去除PageRank算法需要的前提2，增加考慮了用戶從一個網頁直接跳轉到非直接相鄰的但是內容相關的另外一個網頁的情況。

2.3 改進HITS算法

1) 改進HITS算法中的第Ⅰ問題:

提取根集S中的每個文檔的前若干量的詞語，串連起來作為查詢主題T，計算每個文檔的主題相似度，根據不同的閾值進行刷選，閾值可以選擇所有文檔相似度的中值、根集文檔相似度的中值或最大文檔相似度。根據不同閾值進行處理，刪除不滿足條件的文檔。

2) 改進HITS算法中的第Ⅱ問題:

假定主機A上有k個網頁指向主機B上的某個文檔d，則A上的k個文檔對B的Authority貢獻值總共為1，每個文檔貢獻1/k，而不是HITS中的每個文檔貢獻1，總共貢獻k。類似的，對于Hub值，假定主機A上某個文檔t指向主機B上的m個文檔，則B上m個文檔對t的Hub值總共貢獻1，每個文檔貢獻1/m。

3) 改進HITS算法中的第Ⅲ問題(TKC問題)

得到根集并且擴展為網頁集合T，除去孤立節點;

從集合T構造無向圖G’=(Vh，Ua，E)

Vh = { Sh | S∈T and out-degree(S) > 0 } ( G’的Hub邊). (5)

Ua = { Sa | S∈T and in-degree(S) > 0 } (G’的Authority邊).(6)

E= { (Sh ， Sa)}

這就定義了2條馬爾可夫鏈鏈，Authority鏈和Hub鏈。

以上改進算法并非完美算法，仍然有改進的空間，如計算網頁的Authority值時，只考慮網頁在直接相鄰網頁集中的受歡迎程度，忽略其它網頁對它的影響等等。

3 驗證與結果

自行開發搜索引擎系統，對以上HITS算法和改進算法進行測試。

3.1 測試數據

使用搜索引擎中的網絡爬蟲程序抓取網頁，收集近百個網站20多萬網頁。對這些網頁進行分析處理，并加以保存。

先為這些信息按HITS算法建立索引，保存在索引文件夾中。通過這些索引構建搜索器，將該索引映射到內存中，對提交的查詢關鍵字進行快速檢索。再對網頁信息按改進的算法優化索引，并保存在新的索引文件夾中。

3.2 測試結果

1)生成基礎集的質量方面

表2為改進算法與HITS算法生成基礎集質量比較。

2)搜索質量

用不同算法，搜索上述關鍵詞的前20名鏈接網頁加以排序，判斷這些網頁是否符合關鍵詞。

表3為改進算法和HITS算法搜索質量比較。

3)測試結論:用改進算法進行鏈接搜索，其結果較HITS算法更令人滿意。

4 結束語

本文就當前搜索引擎的鏈接問題分析了2種算法，同時對這2種算法的缺陷提出了改進的措施，使搜索引擎的主題鏈接在性能上有很大提高。

當然，關于搜索引擎的鏈接結構，可探討的問題還有許多，可總結的算法也有很多，以上2種算法還有未及之處，比如沒有有效的方法準確判定鏈接是否包含重要的信息、查詢的分類沒有明確界限等等。如果算法要取得更好的效果，還需要繼續做深入的研究。

參考文獻:

[1] 丁一.Web上基于特定主題的RG-HITS算法研究[J].現代圖書情報技術，2005(6).

[2] 王曉宇，周傲.萬維網的鏈接結構分析及其應用綜述[J].軟件學報，2003(10).