HITS算法

互联网术语

HITS 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。

英文全称

Hyperlink-Induced Topic Search

算法由来

具体解释

按照HITS算法，用户输入关键词后，算法对返回的匹配页面计算两种值，一种是枢纽值（Hub Scores），另一种是权威值(Authority Scores),这两种值是互相依存、互相影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值是指所有导入链接所在的页面中枢纽之和。

一个网页重要性的分析的算法。

通常HITS算法是作用在一定范围的，比如一个以程序开发为主题网页，指向另一个以程序开发为主题的网页，则另一个网页的重要性就可能比较高，但是指向另一个购物类的网页则不一定。

在限定范围之后根据网页的出度和入度建立一个矩阵，通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。

Hits算法

描述

HITS(Hyperlink – Induced Topic Search) 算法是利用HubPAuthority的搜索方法,

具体算法如下:

将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合中取前n个网页(如n=200)，作为根集合(root set)，记为S，则S满足：

1.S中的网页数量较少

2.S中的网页是与查询q相关的网页

3.S中的网页包含较多的权威(Authority)网页

通过向S 中加入被S 引用的网页和引用S 的网页,将S 扩展成一个更大的集合T. 以T 中的Hub 网页为顶点集V1 ,以权威网页为顶点集V2 。

V1 中的网页到V2 中的网页的超链接为边集E ,形成一个二分有向图. 对V1 中的任一个顶点v ,用h ( v) 表示网页v 的Hub 值,且h ( v)收敛;对V2 中的顶点u ,用a ( u) 表示网页的Authority 值。

开始时h ( v) = a ( u) = 1 ,对u 执行I 操作,修改它的a ( u) ,对v执行O操作,修改它的h ( v) ,然后规范化a ( u),h ( v) ,如此不断的重复计算下面的I操作和O操作,直到a ( u),h(v)收敛。

其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代对a ( u) 、h ( v) 进行规范化处理: 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

拓展研究

理解HITS算法是Web结构挖掘中最具有权威性和使用最广泛的算法。HITS(Hypertext-InducedTopic Search)算法是利用Web的链接结构进行挖掘典型算法，其核心思想是建立在页面链接关系的基础上，对链接结构的改进算法。HITS算法通过两个评价权值——内容权威度（Authority）和链接权威度（Hub）来对网页质量进行评估。其基本思想是利用页面之间的引用链来挖掘隐含在其中的有用信息（如权威性），具有计算简单且效率高的特点。HITS算法认为对每一个网页应该将其内容权威度和链接权威度分开来考虑，在对网页内容权威度做出评价的基础上再对页面的链接权威度进行评价，然后给出该页面的综合评价。内容权威度与网页自身直接提供内容信息的质量相关，被越多网页所引用的网页，其内容权威度越高；链接权威度与网页提供的超链接页面的质量相关，引用越多高质量页面的网页，其链接权威度越高。

首先，它完全将网页的内容或文本排除在外，仅考虑网页之间的链接结构来分析页面的权威性，这与现实网络中的权威页面相比，其不科学性显而易见。然而HITS算法也有其明显的不足。因为权威页面必须针对某一主题或关键词而言。例如某一页面对一确定主题具有较大权威性，但这并不意味在其他与其无关的主题方面同样具有权威性。其次一个页面对另一页面的引用有多种情况，其中包含了一页面对另一页面的认可，但除此之外也有其他目的链接，如为了导航或为了付费广告。就HITS算法的思想与实现过程做了细致的研究与概括。而HITS算法在实现过程中均没有考虑以上情况．导致了结果与目标的差距。

对HITS算法的第二个不足，即非正常目的的引用．在HITS算法看来，也误认为是正常引用，导致实际结果与目标的出入。针对前面第一种不足，就有相关的学者提出了一种利用超链文字及其周围文字与关键字相匹配而计算超链权值的方法，并引入系数对周围文字和超链文字进行权值的相对控制，很好地将页面文本信息引入到HITS算法，提高了算法的可靠性，并在现实中取得了很好的效果。

后来，经过不断的改进。HITS算法又引入了时间参数，即利用对一链接引用的时间长短来评价是否为正常引用。因为非正常链接其引用时间肯定不会很长（如交换链接、广告链接），相反，如果一页面对另一页面的链接时间较长，则必然反映此页面就是用户的寻找页面。即目标页面或至少是正常引用。

如设定访问时间少于1分钟者为非正常引用。如果设定时间阀值，则可以将非正常引用的链接在HITS算法的实现过程中筛选出来。另外可构造时间访问函数，控制权威页面的相对大小。如随访问时间的增大而其权威性也逐渐非线性增大．这样可为HITS算法的权威页面提供更合理、更科学的解释。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省