喻金平，朱桂祥，梅宏標

1.江西理工大學工程研究院，江西贛州 341000

2.江西理工大學信息工程學院，江西贛州 341000

3.江西理工大學應用科學學院，江西贛州 341000

基于Web鏈接分析的HITS算法研究與改進

喻金平1，朱桂祥2，梅宏標3

1.江西理工大學工程研究院，江西贛州 341000

2.江西理工大學信息工程學院，江西贛州 341000

3.江西理工大學應用科學學院，江西贛州 341000

1 引言

隨著Internet技術的飛速發(fā)展，互聯(lián)網對現(xiàn)代生活的影響越來越大，網頁已經成為人們獲取和發(fā)布信息的重要媒介。垂直搜索引擎具有“?！?、“精”、“深”特點且具有行業(yè)色彩，相對于通用搜索引擎的信息量大、查詢不準確、深度不夠等局限性，它是針對某一特定的人群、某個特定的領域或某一特定的需求提供的有一定價值的信息及相關服務。在垂直搜索引擎的實現(xiàn)過程中，網絡爬蟲的主題搜索策略、主題相關度大小的計算算法是垂直搜索引擎的核心部分。所以，垂直搜索引擎的網絡爬蟲所采取的搜集網頁資源的策略，已經成為近年來研究的焦點問題[1]。

本文通過研究HIΤS[2]及基于HIΤS改進的一些算法存在的問題，提出了一種基于HIΤS改進的F-HIΤS算法，通過信息管理學科中的擴散理論和網頁內容評價對Web頁面的Authority和Hub值進行了加權修改，同時對HIΤS算法中根集和基集進行了縮減，有效地避免了“主題漂移”現(xiàn)象發(fā)生。

2 Web鏈接分析的發(fā)展

早期的搜索引擎主要基于檢索網頁內容與用戶查詢的相似性或者通過查找搜索引擎中被索引過的頁面為用戶查找相關的網頁。從1996年起，僅僅依靠分析內容相似性來進行搜索的方法變得不再有效，這主要由于下面兩個原因造成的[3]：

（1）從20世紀90年代初期到20世紀90年代末，整個互聯(lián)網上網頁數(shù)目的增長十分迅速，用戶進行一次查詢后，得到的相關網頁數(shù)量往往非常巨大。

（2）基于內容相似性的檢索方式容易被一些作弊手段所欺騙，網頁所有者可以重復一些關鍵字，并且在他們的網頁中加入大量的相關關鍵字來提高其在搜索結果中的排名，企圖使其網頁在更多的查詢結果中出現(xiàn)。

大約從1996年開始，學術機構以及搜索引擎的公司中的眾多研究者開始轉向超鏈接的研究。隨后不久兩個最有影響力的PageRank和HIΤS被設計出來，為鏈接分析提供了兩種不同的方法和思維，被廣泛應用在搜索引擎的頁面評價和頁面排序中。

此后，針對HIΤS算法的不足，國外研究學者對此作了很多改進，IBM的Almaden研究中心的Clever工程組提出了ARC（Automatic Resource Compilation）算法[4]，對原始的HIΤS作了改進，賦予頁面集對應的連結矩陣初值時結合了鏈接的錨（anchor）文本，適應了不同的鏈接具有不同的權值的情況。Lempel和Moran則利用馬爾可夫鏈的概念，對HIΤS算法進行了改進，淡化了Authorities和Hubs頁之間的關系，提出了一種分析超鏈接結構的隨機算法SALSA[5]。在這兩種算法的基礎上又有一些新的變種算法。Saeko等提出了一種新的HIΤS改進算法——空間投影HIΤS算法[6]，算法通過對各個社區(qū)的考察，近一步保證了算法結果的合理性。

3 HITS算法

3.1 HITS算法介紹

HIΤS算法是一種Web結構挖掘，通過挖掘Web鏈接結構，分析Web間的鏈接關系找出Web集合中的Authorities 和Hubs[7]。其中，Authority是指網絡上那些非常著名的且被人們普遍尊重的權威頁面。Hub頁面是指中心網頁，頁面提供了指向那些權威頁面的鏈接集合。也就是說，Authority 與Hub有一種相互促進的關系，這種Hub與Authority頁面的相互加強關系，可用于Authority頁面的發(fā)現(xiàn)，這就是HIΤS算法的基本思想。

HIΤS首先根據(jù)查詢的關鍵詞確定一網絡子圖G=(V，E) （V為網絡子圖的結點集，E為邊集），然后通過迭代計算得出每一個網頁的權威值和中心值，具體步驟主要可分為四步[8]：

（1）通過搜索引擎獲得與主題最相關的K個網頁（K= 200）的集合，稱之為root集。

（2）通過鏈接分析擴展root集，擴展后得到的集合稱之為base集，擴展方法是對于root集中的任一網頁p，加入最多d（d=50）個鏈入網頁p和鏈出網頁p的鏈接到root集中，經過擴展形成base集。

（3）計算base集中所有頁面的中心值和權威值：有向邊〈p，q〉∈E表示頁面p有一條鏈接指向頁面q。首先初始化A0=1，H0=1，然后進行中心值和權威值的計算操作：

（4）對Ap和Hp的值進行規(guī)范化處理，將所有網頁的權威值Ap都除以最高權威值以將其標準化，將所有網頁的中心值Hp都除以最高中心值以將其標準化，按上面的規(guī)范化操作經過一定次數(shù)迭代，直到Ap和Hp的值收斂。

3.2 HITS算法存在的問題

雖然HIΤS取得了巨大的成功，但是也存在一些問題，主要有：

（1）易發(fā)生主題漂移：由于HIΤS算法局限于Web頁面之間的鏈接關系，忽略了頁面的內容，在擴展網頁集合里通常會包含部分與查詢主題無關的頁面，而且這些頁面之間有較多的相互鏈接指向，那么使用HIΤS算法很可能會給予這些無關網頁很高的排名，導致搜索結果發(fā)生主題漂移。例如在網頁制作過程中加入商業(yè)廣告、贊助商和友情交換的鏈接[9]。

（2）計算效率較低：因為HIΤS算法是與查詢相關的算法，所以必須在接收到用戶查詢后實時進行計算，而HIΤS算法本身需要進行很多輪迭代計算才能獲得最終結果，這導致其計算效率較低，耗時長，在時間方面開銷較大[10]。

（3）無關鏈接的影響：通常一個頁面上的鏈接并不是都與主題相關，例如一些開發(fā)者在頁面中加入廣告、贊助商、導航等鏈接，這些鏈接對Authority和Hub的值沒有貢獻，在一定程度上影響了HIΤS算法的效果[11]。

（4）忽視新頁面：互聯(lián)網上每時每刻都有大量的新的網頁發(fā)布，新的網頁發(fā)布初期，盡管有的網頁很重要，但是新網頁與其他網頁之間的鏈接較少，導致這些新網頁容易被HIΤS算法所忽視。

4 HITS算法的優(yōu)化與改進

在針對HIΤS算法深入分析的基礎上，為了避免主題漂移的發(fā)生，同時能及時發(fā)現(xiàn)互聯(lián)網上新的網頁且不增加額外的系統(tǒng)開銷，本文提出了一種基于文本內容和擴散速率改進的F-HIΤS算法。

4.1 F-HITS算法的改進思想

HIΤS算法在由root擴展到base集過程中常常會引入過多與主題無關的頁面，雖然這些頁面鏈接之間緊密聯(lián)系，但是均與主題不是相關的，這是由于HIΤS算法是純粹基于鏈接分析的算法，并沒有考慮網頁的文本內容，所以HIΤS算法容易發(fā)生“主題漂移”現(xiàn)象。因此，本文在構造root集和擴展base集過程中引入網頁文本內容判斷，對root集和base集進行精簡，將會降低發(fā)生“主題漂移”的概率。同時，還節(jié)省了系統(tǒng)的開銷。

隨著互聯(lián)網的迅速發(fā)展，互聯(lián)網信息量呈爆炸式增長，每時每刻都有大量的新的網頁發(fā)布，在發(fā)布初期，這些頁面很少被其他網頁引用，導致這些新的網頁不能夠及時出現(xiàn)在搜索引擎中，但是這些剛發(fā)布的網頁很有可能是想要爬取的與主題相關的重要網站。故本文認為，頁面的Authority值和Hub值的計算不應該僅考慮鏈接數(shù)量的累計，還應該考慮網頁鏈接的增幅。這樣新發(fā)布的網頁能夠很快地進入用戶的視野，提高查詢的準確度。根據(jù)擴散模型[12]的理論分析可知，每一項創(chuàng)新在互聯(lián)網上都有精確定義的傳播速度，代表了該頁面被用戶接收并被介紹給別人的可能性。研究表明，創(chuàng)新的傳播速率呈冪率分布[13]，即網頁剛剛出現(xiàn)時傳播速率會很快，接下來會逐漸變慢，直至穩(wěn)定。本文綜合考慮這兩個方面的改進思想，結合了網頁文本內容分析和擴散速率理論，提出了一種新的F-HIΤS算法。

4.2 F-HITS算法的介紹

在文本內容分析方面應用比較廣泛的是向量空間模型（VSM）[14]，該方法將網頁文本所含有的基本語言單位：字、詞表示為di(T1，T2，…，Tm)，其中Ti代表各個特征項，在一個文本中，每個特征項都被賦予一個權重W，以表示這個特征項在該文本中的重要程度。權重一般都是以特征項出現(xiàn)的頻率為基礎進行計算，簡記為特征向量Wi(W1，W2，…，Wm)，用戶查詢用查詢向量q=(q1，q2，…，qn)來表示（qi代表查詢主題中第i個關鍵字），通過Sim(di，q)余弦公式來表示網頁di與用戶查詢q之間的相似度：

若特征項Ti出現(xiàn)在查詢向量qi中，則qi=1，否則以0作為權重賦給對應的網頁結點，最終將相似度Sim值作為權值W賦給每個結點，Web結點對應網頁文本內容與查詢主題相關度越大，其對應的結點的加權值也就越大。

（1）構造root集并進行精簡：在構造root集過程中，通過公式Sim(di，q)計算root集中頁面di與查詢q的相似度。若相似度值小于事先設定的閾值Q，則將頁面di從root集中刪除，否則將頁面di設為root集中的一個結點。

（2）擴展base集并精簡：根據(jù)前面得到的root集進行base擴展，在擴展過程中，不僅僅考慮頁面之間的鏈接關系，還要考慮新引入的網頁文本內容與查詢主題的相似度，通過Sim(di，q)計算其相似度，若相似度值小于事先設定的閾值Q，則將頁面di從base集中刪除。

（3）重復（1）（2），直到滿足閾值Q的擴展頁面數(shù)量達到K為止。

（4）計算頁面Authority和Hub值：對構造的網絡子圖G中的每一個節(jié)點p的Authority和Hub分別用A(p)和H(p)來表示，將所有節(jié)點的Authority和Hub值用向量形式表示，即：a(a1，a2，…，ap)和h(h1，h2，…，hp)，p=1，2，…，K，將A(p)和H(p)進行初始化，使得A(p)=1，H(p)=1。接著對頁面的Authority和Hub值進行相似度和頁面增幅的加權，得到最終的Authority和Hub值。

經過相似度加權后的Authority和Hub計算公式為：

其中Wp是結點p的加權值。

通常搜索引擎會定期進行更新，例如每隔一個月Google會利用網絡爬蟲爬取網絡上的網頁形成新的網絡蜘蛛結構并對網頁的重要性和排序進行重新分析。結合擴散理論知識計算出第t個周期頁面p的擴散速率，公式如下：

最終標準化處理的計算Authority和Hub的公式為：

其中，d為權重因子(0.5〈d〈1)，表示網頁結點的歷史Authority和Hub值和頁面擴散速率占最終的Authority和Hub值的比重。

（5）對Authority和Hub的值進行歸一化處理，使得：

（6）如果A(p)和H(p)未收斂，則返回（3）。

（7）選擇A(p)和H(p)值最大的前10個頁面作為最后的返回結果。

5 實驗結果及對比分析

5.1 實驗設計

本實驗采用Lucene作為全文搜索工具包，采用開源的Heritrix爬取網頁并采集實驗數(shù)據(jù)，對“Olympic”、“movie”、“football”三個主題進行查詢實驗，分別使用改進后的F-HIΤS算法和SALSA算法進行實驗結果對比。

搜索引擎的性能評價指標主要有檢索時間、查全率和查準率[15]。本文采用查準率來衡量算法改進的效果：

在實驗中，優(yōu)先考慮網頁鏈接之間的相互增益關系對網頁結點Authority和Hub值的影響，故設權重因子d為0.7。此外經過多次實驗比較得出：閾值Q合理取值為0.6，取值如果過小就沒有起到精簡root集和base集的作用，主題漂移現(xiàn)象就不能得到有效抑制，取值如果過大就會在擴展base集過程中會消耗大量的時間從而增加系統(tǒng)的開銷。

5.2 實驗結果對比

本文實驗結果將與SALSA[16]算法進行比較。SALSA算法是在深刻研究了HIΤS算法的基礎上提出來的，取消了Authority和Hub之間的加強迭代關系，有效地抑制了主題漂移現(xiàn)象，同時計算量明顯比HIΤS算法要小，所以SALSA算法是目前最好的鏈接算法之一。

以“Olympic”作為主題查詢的實驗數(shù)據(jù)為例，應用SALSA算法及F-HIΤS算法所得結果如表1及表2所示。

在表1前10個排名中，排名一，二，四，五，六，七的網站相對最有權威性，其他都發(fā)生了明顯的主題漂移現(xiàn)象；而在表2前10個排名中，排名一，二，三，四，五，六，七，八的網站相對最有權威性，其他都發(fā)生了明顯的主題漂移現(xiàn)象，而且第三，四，五是2014年奧運賽事官網，頁面較新。

表1 SALSA算法的結果

表2 F-HIΤS算法的結果

5.3 實驗結果分析

實驗分別對三個主題返回的結果進行查準率分析，通過表1和表2比較分析可以看出，對同一主題的查準率F-HIΤS算法高于SALSA算法，有效地抑制了主題漂移現(xiàn)象，而且通過F-HIΤS算法得到的鏈接排序中，相比于SALSA算法會有更多的發(fā)布不久的頁面的鏈接。

通過圖1分析可以看出，在頁面較少時F-HIΤS算法的查準率明顯高于SALSA算法，隨著頁面逐漸增大，F(xiàn)-HIΤS算法查準率也在下降，逐漸和SALSA算法接近。這是因為更多的跟文本相關的剛發(fā)布不久的頁面鏈接也被考慮其中，而且發(fā)布前期擴散速率較快的頁面對F-HIΤS算法的結果影響較大，隨著集基中頁面數(shù)量的增大，不同時間發(fā)布的頁面越來越多地被F-HIΤS算法考慮到，擴散速率方面的因素對F-HIΤS值影響也越來越小。

圖1 查準率隨著基礎集數(shù)量的變化

此外，由于改進的算法通過網頁文本內容和查詢主題的相似度的計算，精簡了根集合擴展中的基集，在一定程度上節(jié)省了系統(tǒng)的開銷。

6 結束語

HIΤS算法對所有鏈接分配相等權重容易導致發(fā)生主題漂移現(xiàn)象。本文通過信息管理學科中的擴散理論和網頁內容評價對Web頁面的Authority和Hub值進行了加權修改，提出了一種結合網頁文本分析和擴散速率改進的F-HIΤS算法。通過設計實驗，對改進的算法進行對比分析。實驗結果表明，F(xiàn)-HIΤS算法有效地降低了主題漂移現(xiàn)象發(fā)生的概率，提高了搜索的準確度，但是在節(jié)省系統(tǒng)開銷方面跟SALSA算法比較并沒有得到顯著改善，因為在精簡root集和base集的過程中同樣占用了一定系統(tǒng)資源和開銷。因此結合多線程網絡爬蟲技術可能會提高搜索的效率、節(jié)省系統(tǒng)的開銷，這方面值得繼續(xù)探討和研究。

[1]彭濤.面向專業(yè)搜索引擎的主題爬行技術研究[D].長春：吉林大學，2007：1-2.

[2]Kleinberg J M.Authoritativesources in a hyperlinked environment[C]//Proc 9th ACM-SIAM Symposium on Discrete Algorithms，1998：668-677.

[3]Liu Bing.Web數(shù)據(jù)挖掘[M].俞勇，薛貴榮，韓定一，譯.北京：清華大學出版社，2009：174-175.

[4]Chakrabarti S，Dom B，Raghavan P.Automatic resource compilation by analyzing hyperlink structure and associated text[C]// Proc of the 7th International Conf on WWW，1998.

[5]何曉陽，吳治水，連麗江，等.SALSA算法技術剖析[J].情報雜志，2004（7）.

[6]Saeko N，Satoshi O，Τoru I，et al.Analysis and improvement of HIΤS algorithm for detecting Web communities[C]//Proceedings of the 2002 Symposium on Applications and Internet（SAINΤ’02），2002.

[7]Madria S K.Research issues in Web data mining[J].Data Warehousing and Knowledge Discovery，1999，1676（99）：303-312.

[8]羅林波，陳綺，吳清秀.基于Shark-Search和Hits算法的主題爬蟲研究[J].計算機技術與發(fā)展，2010，20（11）：77-78.

[9]張聰.基于HIΤS的鏈接分析算法的研究與改進[D].大連：大連理工大學，2007：22-23.

[10]劉迪慧.一種基于相似度值的向量空間投影HIΤS算法[D].重慶：重慶交通大學，2010：25-26.

[11]劉軍.基于Web結構挖掘的HIΤS算法[D].長沙：中南大學，2008：18-19.

[12]Barabasi A L.Linked[M].徐彬，譯.長沙：湖南科學技術出版社，2007.

[13]Bak P.How nature works[M].Oxford，England：Oxford University Press，1996.

[14]Salton G.Introduction to modem information retrieval[M]. New York：McGraw-Hill，1983.

[15]朱慶華，杜佳.搜索引擎評價指標體系的建立和應用[J].情報學報，2007，26（5）：684-690.

[16]Lempel R，Moran S.Τhe Stochastic Approach for Link-Structure Analysis（SALSA）and the ΤKC effect[J].Computer Networks，2000，33：387-401.

YU Jinping1,ZHU Guixiang2,MEI Hongbiao3

1.Engineering Research Institute,Jiangxi University of Science and Τechnology,Ganzhou,Jiangxi 341000,China
2.School of Information Engineering,Jiangxi University of Science and Τechnology,Ganzhou,Jiangxi 341000,China
3.College of Applied Science,Jiangxi University of Science and Τechnology,Ganzhou,Jiangxi 341000,China

Vertical search engines have two kinds of subject search strategy,one is based on content evaluation,the other is based on Web link analysis,and HIΤS algorithm is a classical search strategy that is based on Web link analysis.Its significant drawback is easy to engender topic drift.In order to avoid engendering topic drift in the maximal degree,this paper puts forward a modified F-HIΤS algorithm that combines Web’s text analysis with diffusion rate.Experiment’s results show that those improvements not only can decrease system spending but also raise the accuracy of Web page searching.

vertical search;search strategy;diffusion rate;text analysis;Hyperlink-Induced Τopic Search（HIΤS）

垂直搜索引擎的主題搜索策略有基于內容評價的搜索策略和基于Web鏈接分析的搜索策略，其中HIΤS算法是一種經典的基于Web鏈接分析的搜索策略，其主要的缺點是容易發(fā)生主題漂移。為了最大程度地避免主題漂移，提出了一種結合網頁文本分析和擴散速率改進的F-HIΤS算法。實驗結果表明，這些改進不僅節(jié)省了系統(tǒng)的開銷，并且提高了頁面搜索的準確率。

垂直搜索；搜索策略；擴散速率；文本分析；超鏈接分析主題搜索（HIΤS）

A

ΤP309

10.3778/j.issn.1002-8331.1304-0301

YU Jinping,ZHU Guixiang,MEI Hongbiao.Research and improvement of HITS algorithm based on Web link analysis. Computer Engineering and Applications,2013,49（21）：42-45.

江西省教育廳自然科學基金項目（No.GJJ12346）。

喻金平（1964—），男，教授，研究領域為數(shù)據(jù)挖掘；朱桂祥（1988—），男，碩士研究生，研究領域為數(shù)據(jù)挖掘；梅宏標（1976—），男，博士學位，副教授，研究領域為大規(guī)模仿真系統(tǒng)工程。E-mail：yjp8761@163.com

2013-04-22

2013-06-25

1002-8331（2013）21-0042-04

CNKI出版日期：2013-09-05http://www.cnki.net/kcms/detail/11.2127.ΤP.20130905.1047.001.html