HITS算法的基本理论

HITS算法是利用Web页面链接结构进行权威面页挖掘的一种最权威、最广泛的算法．目前被许多高性能的搜索引擎广泛使用。其基本思想为：
①将页面分为两种类型，一种为表达某一主题的权威页面，称为Authority页面，另一种为能把这些Authority页面联结在一起的页面，称为Hub页面，图l和图2表示了这两种类型的页面。而Authority和之
间相互优化的关系构成了HITS 算法的基础。利用Hub页面找出权威页面的过程为：首先，由查询关键词借助传统的搜索引擎得到一初始结果集．作为根集(root set)，也称为开始集(start set)。由于这些
页面中的许多页面是假定与搜索内容相关的，因此它们中应包含指向最权威页面的指针。故此，根集可进一步扩展为基本集 ase set)，它包含了所有由根集中的页所指向的页，以及所有指向根集页的页。
② 开始权重传播。这一过程是递归过程，用于决定Hub与权威权重的值。先为基本集中的每一个页面设定一个非负的权威权重印和非负的Hub权重hp，并将其初始化为同一常数。权重可按如下公式计算：


公式(1)反映了若一个页面由很多好的Hub所指，则其权威权重会相应增加；公式(2)反映了若一个页面指向好的权威页，则Hub权重也会相应增加。最后．HITS算法输出一组具有较大Hub权重的页面和具有较大权威权重的页面。
如果甩有向图来描述Web的链接结构，则其包含了一个节点集合和有向图的边的集合．而此节点集合中的子集S和S中的所有节点和节点之间的边构成了Web的子图。而HITS 算法就是为每个页面引入两个权值：Authority权值和Hub权值，最后输出具有最大的页面。
可以合页面标号{1，2，．．_n}并且定义它们的nn阶邻接矩阵，如果页面I指向页面j，则矩阵中的项(Ij)为1，否则为0。同样把所有的Authority权值和Hub权值定义为向量，x=(xl，x2⋯xn)，y=(yl，y2 ．yn)，则式(1)(2)的矩阵形式为：


因此向量x,y均可由式(3)(4)经过多次迭代而得到。根据线性代数理论．迭代序开经过标准化最终收敛于矩阵的特征向量，即计算机的Authority权值和Hub权值是页面集合的固有属性，并不是由初始向量和参数的选择决定的【2】。文章来源：http://www.youniku.com/post/95.html 转载请保留，谢谢！