图算法之HITS算法

算法起源

  HITS算法的全称是“基于超链接的主题搜索”(Hyperlink-Induced Topic Search)，该算法由Jon Kleinberg于1999年提出，与PageRank算法一样，也是一种用于对网页进行排序的算法。与PageRank不同的是，HITS将网页分成两类，即：Hub页面和Authority页面。其中Hub页面类似于常见的门户网站，像hao123首页之类的，它提供了大量高质量的网页链接；而Authority页面更像是用户希望访问的网站，比如搜索的时候我们希望用百度，购物的时候我们希望进入淘宝和京东等。Hub页面相当于充当了一个中间枢纽的角色，对于用户而言，他们更关注高Authority的网页。下面接单介绍一下HITS算法的原理和求解过程。

算法原理

   HITS采用互相增强原理，并基于以下两个假设：

一个高质量的authority页面会被很多高质量的hub页面所指向。
一个高质量的hub页面会指向很多高质量的authority页面。

  这两个假设也是非常好理解，利用上述两个基本假设及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显的变化为止。其中每个网页的Authority值和Hub值的计算公式如下：

算法具体过程大致可分为以下五个步骤：

1. 将各节点的auth值和hub值均设为1。
2. 利用公式计算并更新每个节点的auth值
3. 利用更新的auth值，计算并更新节点的hub值
4. 将auth值和hub值归一化。
5. 重复2~4，直至收敛或达到停止迭代条件。

好了，HITS算法的原理其实就这么点，十分通俗易懂。

算法不足（参考：HITS算法--从原理到实现）

主题漂移

在算法原理部分我们介绍了HITS算法是如何生成初始集合Gσ。从根集合Rσ我们通过链接添加网页的方法进行扩展，但这也很可能添加进与搜索主题无关的网页。若是这部分网页中又恰恰有着一些高质量的authority页面，则很有可能返回给用户，降低用户的搜索体验。

作弊网页

试想我们弄一个页面指向很多高质量的authority页面，那么这个页面就成为了一个高质量的hub页面。然后再弄个链接指向自己的搓网页，按照HITS算法，将大大提升自己的搓网页的authority值。

稳定性差

对于一个网页集合，若是删除其中的某条链接，就有可能造成一些网页的hub值和authority值发生巨大变化。

参考：
PageRank算法和HITS算法