HITS authority and hub

HITS（Hyper-link-induced topic search）是由kleinberg提出来的基于连接分析的网页排名算法，描述2种类型的网页：

1、权威性（authority）的网页：对于一个特定的的检索，该网页提供最好的相关信息；

2、目录型（hub）网页:该网页提供很多指向其他高质量权威型的网页链接。

 

由此，我们可以在每个网页上定义“目录型权值”和“权威型权值”2个参数。
1）HITS算法基本思想：
           1：好的hub型网页指向好的authority型网页；
           2：好的authority型网页是由好的hub型网页所指向的网页；
2）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)Ph ( v) ,如此不断的重复计算下面的I操作和O操作,直到a ( u) 。
其中I操作:a ( u) = Σh ( v) ;O 操作: h ( v) = Σa ( u) 。每次迭代对a ( u) 、h ( v) 进行规范化处理: a ( u) = a ( u)PΣ[ a ( q) ]2 ; h ( v) = h ( v)PΣ[ h ( q) ]2 。
HITS算法可以获得比较好的查全率,输出一组具有较大Hub 值的网页和具有较大权威值的网页. 但在实际应用中,HITS算法有以下几个问题:
由S 生成T 的时间开销是很昂贵的,由T 生成有向图也很耗时,需要分别计算网页的APH值,计算量大;网页中广告等无关链接影响A 、H值的计算,降低HITS算法的精度;HITS算法只计算主特征向量,处理不好主题漂移问题;进行窄主题查询时,可能产生主题泛化问题。
相关分析算法大体可以分为4 类:基于随机漫游模型的算法,比如PageRank ,Repution 算法;基于Hub 和Authority 相互加强模型的算法,如HITS 及其变种;基于概率模型的算法,如SALSA ,PHITS;基于贝叶斯模型的算法,如贝叶斯算法. 所有的算法在实际应用中都结合传统的内容分析技术进行优化。Allan Borodin 也指出没有一种算法是完美的,在某些查询下,结果可能很好,在另外的查询下,结果可能很差.将S扩展为基本集合(base set) T，T包含由S指出或指向S的网页。可以设定一个上限如 1000—5000个网页。
开始权重传播。在集合T中计算每个网页的目录型权值和权威型权值。Clever的做法是采用目录型网页和权威型网页相互评价的办法进行递归计算。对于一个网页p，用xp来表示网页p的权威型权值，用yp来表示它的目录型权值，并且用如下公式进行计算：
1.计算各节点的Hub和Authority：
2.赋予每个节点的hub值和authority值都为1。
3.运行Authority更新规则。
4.运行Hub更新规则。
5.Normalize数值，即每个节点的Hub值除所有Hub值之和，每个Authority值除所有Authority值之和。
6.必要时从第二步开始重复。