HITS算法
HITS 算法是由康奈爾大學( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項目中的一部分。
英文全稱
Hyperlink-Induced Topic Search
算法由來
HITS 算法是由康奈爾大學( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項目中的一部分。
具體解釋
按照HITS算法，用戶輸入關(guān)鍵詞后，算法對返回的匹配頁面計算兩種值，一種是樞紐值（Hub Scores），另一種是權(quán)威值(Authority Scores),這兩種值是互相依存、互相影響的。所謂樞紐值，指的是頁面上所有導出鏈接指向頁面的權(quán)威值之和。權(quán)威值是指所有導入鏈接所在的頁面中樞紐之和。
一個網(wǎng)頁重要性的分析的算法。
通常HITS算法是作用在一定范圍的，比如一個以程序開發(fā)為主題網(wǎng)頁，指向另一個以程序開發(fā)為主題的網(wǎng)頁，則另一個網(wǎng)頁的重要性就可能比較高，但是指向另一個購物類的網(wǎng)頁則不一定。
在限定范圍之后根據(jù)網(wǎng)頁的出度和入度建立一個矩陣，通過矩陣的迭代運算和定義收斂的閾值不斷對兩個向量Authority和Hub值進行更新直至收斂。
Hits算法
描述
HITS(Hyperlink – Induced Topic Search) 算法是利用HubPAuthority的搜索方法,
具體算法如下:
將查詢q提交給基于關(guān)鍵字查詢的檢索系統(tǒng)，從返回結(jié)果頁面的集合中取前n個網(wǎng)頁(如n=200)，作為根集合(root set)，記為S，則S滿足：
1.S中的網(wǎng)頁數(shù)量較少
2.S中的網(wǎng)頁是與查詢q相關(guān)的網(wǎng)頁
3.S中的網(wǎng)頁包含較多的權(quán)威(Authority)網(wǎng)頁
通過向S 中加入被S 引用的網(wǎng)頁和引用S 的網(wǎng)頁,將S 擴展成一個更大的集合T. 以T 中的Hub 網(wǎng)頁為頂點集V1 ,以權(quán)威網(wǎng)頁為頂點集V2 。
V1 中的網(wǎng)頁到V2 中的網(wǎng)頁的超鏈接為邊集E ,形成一個二分有向圖. 對V1 中的任一個頂點v ,用h ( v) 表示網(wǎng)頁v 的Hub 值,且h ( v)收斂;對V2 中的頂點u ,用a ( u) 表示網(wǎng)頁的Authority 值。
開始時h ( v) = a ( u) = 1 ,對u 執(zhí)行I 操作,修改它的a ( u) ,對v執(zhí)行O操作,修改它的h ( v) ,然后規(guī)范化a ( u),h ( v) ,如此不斷的重復計算下面的I操作和O操作,直到a ( u),h(v)收斂 。
其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代對a ( u) 、h ( v) 進行規(guī)范化處理: a ( u) = a ( u)/Σ[ a ( q) ]2 ; h ( v) = h ( v)/Σ[ h ( q) ]2 。
偽代碼
HITS算法偽代碼如下：
1G:= set of pages
2for eachpagepinGdo
3p.auth = 1 //p.auth is the authority score of the pagep
4p.hub = 1 //p.hub is the hub score of the pagep
5functionHubsAndAuthorities(G)
6forstepfrom1tokdo// run the algorithm for k steps
7 norm = 0
8for eachpagepinGdo// update all authority values first
9p.auth = 0
10for eachpageqinp.incomingNeighborsdo//p.incomingNeighborsis the set of pages that link top
11p.auth +=q.hub
12 norm += square(p.auth) // calculate the sum of the squared auth values to normalise
13 norm = sqrt(norm)
14for eachpagepinGdo// update the auth scores
15p.auth =p.auth / norm // normalise the auth values
16 norm = 0
17for eachpagepinGdo// then update all hub values
18p.hub =
019for eachpagerinp.outgoingNeighborsdo//p.outgoingNeighborsis the set of pages thatplinks to
20p.hub +=r.auth
21 norm += square(p.hub) // calculate the sum of the squared hub values to normalise
22 norm = sqrt(norm)
23for eachpagepinGdo// then update all hub values
24p.hub =p.hub / norm // normalise the hub values
