HITS算法
HITS 算法是由康奈爾大學(xué)( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項(xiàng)目中的一部分。
英文全稱
Hyperlink-Induced Topic Search
算法由來(lái)
HITS 算法是由康奈爾大學(xué)( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,為IBM 公司阿爾馬登研究中心( IBM Almaden Research Center) 的名為“CLEVER”的研究項(xiàng)目中的一部分。
具體解釋
按照HITS算法，用戶輸入關(guān)鍵詞后，算法對(duì)返回的匹配頁(yè)面計(jì)算兩種值，一種是樞紐值（Hub Scores），另一種是權(quán)威值(Authority Scores),這兩種值是互相依存、互相影響的。所謂樞紐值，指的是頁(yè)面上所有導(dǎo)出鏈接指向頁(yè)面的權(quán)威值之和。權(quán)威值是指所有導(dǎo)入鏈接所在的頁(yè)面中樞紐之和。
一個(gè)網(wǎng)頁(yè)重要性的分析的算法。
通常HITS算法是作用在一定范圍的，比如一個(gè)以程序開(kāi)發(fā)為主題網(wǎng)頁(yè)，指向另一個(gè)以程序開(kāi)發(fā)為主題的網(wǎng)頁(yè)，則另一個(gè)網(wǎng)頁(yè)的重要性就可能比較高，但是指向另一個(gè)購(gòu)物類的網(wǎng)頁(yè)則不一定。
在限定范圍之后根據(jù)網(wǎng)頁(yè)的出度和入度建立一個(gè)矩陣，通過(guò)矩陣的迭代運(yùn)算和定義收斂的閾值不斷對(duì)兩個(gè)向量Authority和Hub值進(jìn)行更新直至收斂。
Hits算法
描述
HITS(Hyperlink – Induced Topic Search) 算法是利用HubPAuthority的搜索方法,
具體算法如下:
將查詢q提交給基于關(guān)鍵字查詢的檢索系統(tǒng)，從返回結(jié)果頁(yè)面的集合中取前n個(gè)網(wǎng)頁(yè)(如n=200)，作為根集合(root set)，記為S，則S滿足：
1.S中的網(wǎng)頁(yè)數(shù)量較少
2.S中的網(wǎng)頁(yè)是與查詢q相關(guān)的網(wǎng)頁(yè)
3.S中的網(wǎng)頁(yè)包含較多的權(quán)威(Authority)網(wǎng)頁(yè)
通過(guò)向S 中加入被S 引用的網(wǎng)頁(yè)和引用S 的網(wǎng)頁(yè),將S 擴(kuò)展成一個(gè)更大的集合T. 以T 中的Hub 網(wǎng)頁(yè)為頂點(diǎn)集V1 ,以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集V2 。
V1 中的網(wǎng)頁(yè)到V2 中的網(wǎng)頁(yè)的超鏈接為邊集E ,形成一個(gè)二分有向圖. 對(duì)V1 中的任一個(gè)頂點(diǎn)v ,用h ( v) 表示網(wǎng)頁(yè)v 的Hub 值,且h ( v)收斂;對(duì)V2 中的頂點(diǎn)u ,用a ( u) 表示網(wǎng)頁(yè)的Authority 值。
開(kāi)始時(shí)h ( v) = a ( u) = 1 ,對(duì)u 執(zhí)行I 操作,修改它的a ( u) ,對(duì)v執(zhí)行O操作,修改它的h ( v) ,然后規(guī)范化a ( u),h ( v) ,如此不斷的重復(fù)計(jì)算下面的I操作和O操作,直到a ( u),h(v)收斂 。
其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代對(duì)a ( u) 、h ( v) 進(jìn)行規(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
