???????????????????????????????????????????????????????????????????????

????????????????????????????????????? 本文節選自《這就是搜索引擎：核心技術詳解》第六章

????? HITS算法也是鏈接分析中非常基礎且重要的算法，目前已被Teoma搜索引擎（www.teoma.com）作為鏈接分析算法在實際中使用。

6.4.1 Hub頁面與Authority頁面

?

???? Hub頁面和Authority頁面是HITS算法最基本的兩個定義。所謂“Authority”頁面，是指與某個領域或者某個話題相關的高質量網頁，比如搜索引擎領域，Google和百度首頁即該領域的高質量網頁，比如視頻領域，優酷和土豆首頁即該領域的高質量網頁。所謂“Hub”頁面，指的是包含了很多指向高質量“Authority”頁面鏈接的網頁，比如hao123首頁可以認為是一個典型的高質量“Hub”網頁。

????? 圖6-11給出了一個“Hub”頁面實例，這個網頁是斯坦福大學計算語言學研究組維護的頁面，這個網頁收集了與統計自然語言處理相關的高質量資源，包括一些著名的開源軟件包及語料庫等，并通過鏈接的方式指向這些資源頁面。這個頁面可以認為是“自然語言處理”這個領域的“Hub”頁面，相應的，被這個頁面指向的資源頁面，大部分是高質量的“Authority”頁面。

?????????????????????????

?????????????????????? ? ? ? ? ? ? ? ? ?? 圖6-11 自然語言處理領域的Hub頁面

?

???? HITS算法的目的即是通過一定的技術手段，在海量網頁中找到與用戶查詢主題相關的高質量“Authority”頁面和“Hub”頁面，尤其是“Authority”頁面，因為這些頁面代表了能夠滿足用戶查詢的高質量內容，搜索引擎以此作為搜索結果返回給用戶。

6.4.2 相互增強關系

??? 很多算法都是建立在一些假設之上的，HITS算法也不例外。HITS算法隱含并利用了2個基本假設：

?????? 基本假設1：一個好的“Authority”頁面會被很多好的“Hub”頁面指向；

?????? 基本假設2：一個好的“Hub”頁面會指向很多好的“Authority”頁面；

到目前為止，無論是從“Hub”或者“Authority”頁面的定義也好，還是從兩個基本假設也好，都能看到一個模糊的描述，即“高質量”或者“好的”，那么什么是“好的”Hub頁面？什么是“好的”Authority頁面？兩個基本假設給出了所謂“好”的定義。

????? 基本假設1說明了什么是“好的”Authority頁面，即被很多好的Hub頁面指向的頁面是好的“Authority”頁面，這里兩個修飾語非常重要：“很多”和“好的”，所謂“很多”，即被越多的Hub頁面指向越好，所謂“好的”，意味著指向本頁面的“Hub”頁面質量越高，則本頁面越好。即綜合了指向本頁面的所有Hub節點的數量和質量因素。

????? 基本假設2則給出了什么是“好的”Hub頁面的說明，即指向很多好的Authority頁面的網頁是好的Hub頁面。同樣的，“很多”和“好的”兩個修飾語很重要，所謂“很多”，即指向的Authority頁面數量越多越好；所謂“好的”，即指向的Authority頁面質量越高，則本頁面越是好的Hub頁面。也即綜合考慮了該頁面有鏈接指向的所有頁面的數量和質量因素。

????? 從以上兩個基本假設可以推導出Hub頁面和Authority頁面之間的相互增強關系（參考圖6-12）， 即某個網頁的Hub質量越高，則其鏈接指向的頁面的Authority質量越好；反過來也是如此，一個網頁的Authority質量越高，則那些有鏈接指向本網頁的頁面Hub質量越高。通過這種相互增強關系不斷迭代計算，即可找出哪些頁面是高質量的Hub頁面，哪些頁面是高質量的Authority頁面。

??????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

??????????????????????????????????????????????????? 圖6-12 相互增強關系

????? ??????????????????????????????????????????????????????

6.4.3 HITS算法

?? ?? HITS算法與Pagerank算法一個顯著的差異是：HITS算法與用戶輸入的查詢請求密切相關，而Pagerank是與查詢無關的全局算法。HITS后續計算步驟都是在接收到用戶查詢后展開的，即是與查詢相關的鏈接分析算法。

?? ?? HITS算法接收到了用戶查詢之后，將查詢提交給某個現有的搜索引擎（或者是自己構造的檢索系統），并在返回的搜索結果中，提取排名靠前的網頁，得到一組與用戶查詢高度相關的初始網頁集合，這個集合被稱作為根集（Root Set）。

????? 在根集的基礎上，HITS算法對網頁集合進行擴充（參考圖6-13），擴充原則是：凡是與根集內網頁有直接鏈接指向關系的網頁都被擴充進來，無論是有鏈接指向根集內頁面也好，或者是根集頁面有鏈接指向的頁面也好，都被擴充進入擴展網頁集合。HITS算法在這個擴充網頁集合內尋找好的“Hub”頁面與好的“Authority”頁面。

???????????????????????????????????????

??????????????????? ??? ? ? ? ? ? ? ? ? ? ? ? ?? ? ??? 圖6-13 根集與擴展集

????? 對于“擴充網頁集合”來說，我們并不知道哪些頁面是好的“Hub”或者好的“Authority”頁面，每個網頁都有潛在的可能，所以對于每個頁面都設立兩個權值，分別來記載這個頁面是好的Hub或者Authority頁面的可能性。在初始情況下，在沒有更多可利用信息前，每個頁面的這兩個權值都是相同的，可以都設置為1。

????? 之后，即可利用上面提到的兩個基本假設，以及相互增強關系等原則進行多輪迭代計算，每輪迭代計算更新每個頁面的兩個權值，直到權值穩定不再發生明顯的變化為止。

???? 圖6-14給出了迭代計算過程中，某個頁面的Hub權值和Authority權值的更新方式。假設以A(i)代表網頁i的Authority權值，以H(i)代表網頁i的Hub權值。在圖6-14的例子中，“擴充網頁集合”有3個網頁有鏈接指向頁面1，同時頁面1有3個鏈接指向其它頁面。那么，網頁1在此輪迭代中的Authority權值即為所有指向網頁1頁面的Hub權值之和；類似的，網頁1的Hub分值即為所指向的頁面的Authority權值之和。

?????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

???????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ?? 圖6-14 ?Hub與Authority權值計算

???????? “擴充網頁集合”內其它頁面也以類似的方式對兩個權值進行更新，當每個頁面的權值都獲得了更新，則完成了一輪迭代計算，此時HITS算法會評估上一輪迭代計算中的權值和本輪迭代之后權值的差異，如果發現總體來說權值沒有明顯變化，說明系統已進入穩定狀態，則可以結束計算。將頁面根據Authority權值得分由高到低排序，取權值最高的若干頁面作為響應用戶查詢的搜索結果輸出。如果比較發現兩輪計算總體權值差異較大，則繼續進入下一輪迭代計算，直到整個系統權值穩定為止。

?????????????????????

6.4.4 ?HITS算法存在的問題

????? HITS算法整體而言是個效果很好的算法，目前不僅應用在搜索引擎領域，而且被“自然語言處理”以及“社交分析”等很多其它計算機領域借鑒使用，并取得了很好的應用效果。盡管如此，最初版本的HITS算法仍然存在一些問題，而后續很多基于HITS算法的鏈接分析方法，也是立足于改進HITS算法存在的這些問題而提出的。

?????? 歸納起來，HITS算法主要在以下幾個方面存在不足：

???? ?? 1.計算效率較低

?????????? 因為HITS算法是與查詢相關的算法，所以必須在接收到用戶查詢后實時進行計算，而HITS算法本身需要進行很多輪迭代計算才能獲得最終結果，這導致其計算效率較低，這是實際應用時必須慎重考慮的問題。

??????? 2.主題漂移問題

????? ??? 如果在擴展網頁集合里包含部分與查詢主題無關的頁面，而且這些頁面之間有較多的相互鏈接指向，那么使用HITS算法很可能會給予這些無關網頁很高的排名，導致搜索結果發生主題漂移，這種現象被稱為“緊密鏈接社區現象”（Tightly-Knit CommunityEffect）。

?? ???? 3.易被作弊者操縱結果

??????? ? HITS從機制上很容易被作弊者操縱，比如作弊者可以建立一個網頁，頁面內容增加很多指向高質量網頁或者著名網站的網址，這就是一個很好的Hub頁面，之后作弊者再將這個網頁鏈接指向作弊網頁，于是可以提升作弊網頁的Authority得分。

??????? 4.結構不穩定

???????? 所謂結構不穩定，就是說在原有的“擴充網頁集合”內，如果添加刪除個別網頁或者改變少數鏈接關系，則HITS算法的排名結果就會有非常大的改變。

?

6.4.5 HITS算法與PageRank算法比較

?

???? HITS算法和PageRank算法可以說是搜索引擎鏈接分析的兩個最基礎且最重要的算法。從以上對兩個算法的介紹可以看出，兩者無論是在基本概念模型還是計算思路以及技術實現細節都有很大的不同，下面對兩者之間的差異進行逐一說明。?? ???

????? 1.HITS算法是與用戶輸入的查詢請求密切相關的，而PageRank與查詢請求無關。所以，HITS算法可以單獨作為相似性計算評價標準，而PageRank必須結合內容相似性計算才可以用來對網頁相關性進行評價；

????? 2.HITS算法因為與用戶查詢密切相關，所以必須在接收到用戶查詢后實時進行計算，計算效率較低；而PageRank則可以在爬蟲抓取完成后離線計算，在線直接使用計算結果，計算效率較高；

????? 3.HITS算法的計算對象數量較少，只需計算擴展集合內網頁之間的鏈接關系；而PageRank是全局性算法，對所有互聯網頁面節點進行處理；

??? ? 4.從兩者的計算效率和處理對象集合大小來比較，PageRank更適合部署在服務器端，而HITS算法更適合部署在客戶端；

?????? 5.HITS算法存在主題泛化問題，所以更適合處理具體化的用戶查詢；而PageRank在處理寬泛的用戶查詢時更有優勢；

????? 6.HITS算法在計算時，對于每個頁面需要計算兩個分值，而PageRank只需計算一個分值即可；在搜索引擎領域，更重視HITS算法計算出的Authority權值，但是在很多應用HITS算法的其它領域，Hub分值也有很重要的作用；

????? 7.從鏈接反作弊的角度來說，PageRank從機制上優于HITS算法，而HITS算法更易遭受鏈接作弊的影響。

????? 8.HITS算法結構不穩定，當對“擴充網頁集合”內鏈接關系作出很小改變，則對最終排名有很大影響；而PageRank相對HITS而言表現穩定，其根本原因在于PageRank計算時的“遠程跳轉”。

總結

以上是生活随笔為你收集整理的搜索引擎链接算法之：HITS算法解析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。