HITS 算法（Hypertext Induced Topic Selection）

HITS 算法（Hypertext Induced Topic Selection）

HITS 算法也是链接分析中非常基础且重要的算法，目前已被Teoma 搜索引擎（）作为链接分析算法在实际中使用。

Hub 页面与Authority 页面

Hub 页面和Authority 页面是HITS 算法最基本的两个定义。所谓Authority 页面，是指与某个领域或者某个话题相关的高质量网页。比如搜索引擎领域，Google 和百度首页即该领域的高质量网页；比如视频领域，优酷和土豆首页即该领域的高质量网页。所谓的Hub页面，指的是包含了很多指向高质量Authority 页面链接的网页，比如hao123 首页可以认为是一个典型的高质量Hub 网页。

图 6-11 给出了一个Hub 页面实例，这个网页是斯坦福大学计算语言学研究组维护的页面，这个网页收集了与统计自然语言处理相关的高质量资源，包括一些著名的开源软件包及语料库等，并通过链接的方式指向这些资源页面。这个页面可以认为是“自然语言处理”这个领域的Hub 页面，相应地，被这个页面指向的资源页面，大部分是高质量的Authority页面。

 

 

 

HITS 算法的目的是通过一定的技术手段，在海量网页中找到与用户查询主题相关的高质量Authority 页面和Hub 页面，尤其是Authority 页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎以此作为搜索结果返回给用户。

相互增强关系

很多算法都是建立在一些假设之上的，HITS 算法也不例外。HITS 算法隐含并利用了两个基本假设：

· 基本假设 1：一个好的Authority 页面会被很多好的Hub 页面指向。

· 基本假设 2：一个好的Hub 页面会指向很多好的Authority 页面。

到目前为止，无论是从Hub 页面或者Authority 页面的定义也好，还是从两个基本假设也好，都能看到一个模糊的描述，即“高质量”或者“好的”，那么什么是“好的”Hub 页面？什么是“好的”Authority 页面？两个基本假设给出了所谓“好”的定义。

基本假设 1 说明了什么是“好的”Authority 页面，即被很多好的Hub 页面指向的页面是好的Authority 页面，这里两个修饰语非常重要：“很多”和“好的”，所谓“很多”，即被越多的Hub 页面指向越好，所谓“好的”，意味着指向该页面的Hub 页面质量越高，则页面越好。这综合了指向本页面的所有Hub 节点的数量和质量因素。

基本假设 2 则给出了什么是“好的”Hub 页面的说明，即指向很多好的Authority 页面的网页是好的Hub 页面。同样地，“很多”和“好的”两个修饰语很重要，所谓“很多”，即指向的Authority 页面数量越多越好；所谓“好的”，即指向的Authority 页面质量越高，则该页面越是好的Hub 页面。这也综合考虑了该页面有链接指向的所有页面的数量和质量因素。

从以上两个基本假设可以推导出 Hub 页面和Authority 页面之间的相互增强关系， 即某个网页的 Hub 质量越高，则其链接指向的页面的Authority 质量越好；反过来也是如此，一个网页的Authority 质量越高，则那些有链接指向本网页的页面Hub 质量越高。通过这种相互增强关系不断迭代计算，即可找出哪些页面是高质量的Hub 页面，哪些页面是高质量的Authority 页面。

 

HITS 算法

HITS 算法与PageRank 算法一个显著的差异是：HITS 算法与用户输入的查询请求密切相关，而PageRank 算法是与查询无关的全局算法。HITS 后续计算步骤都是在接收到用户查询后展开的，即是与查询相关的链接分析算法。

HITS 算法接收到了用户查询之后，将查询提交给某个现有的搜索引擎（或者是自己构造的检索系统），并在返回的搜索结果中，提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称做根集（Root Set）。

在根集的基础上，HITS 算法对网页集合进行扩充，扩充原则是：凡是与根集内网页有直接链接指向关系的网页都被扩充进来，无论是有链接指向根集内页面也好，或者是根集页面有链接指向的页面也好，都被扩充进入扩展网页集合。HITS 算法在这个扩展网页集合内寻找好的Hub 页面与好的Authority 页面。

 

对于扩展网页集合来说，我们并不知道哪些页面是好的Hub 页面或者好的Authority页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub 页面或者Authority 页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这两个权值都是相同的，可以都设置为1。

之后，即可利用上面提到的两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显的变化为止。

图 6-14 给出了迭代计算过程中，某个页面的Hub 权值和Authority 权值的更新方式。假设以A(i)代表网页i 的Authority 权值，以H(i)代表网页i 的Hub 权值。在如图6-14 所示的例子中，扩展网页集合有3 个网页有链接指向页面1，同时页面1 有3 个链接指向其他页面。那么，网页1 在此轮迭代中的Authority 权值即为所有指向网页1 页面的Hub 权值之和；类似地，网页1 的Hub 分值即为所指向的页面的Authority 权值之和。

扩展网页集合内其他页面也以类似的方式对两个权值进行更新，当每个页面的权值都获得了更新，则完成了一轮迭代计算，此时HITS 算法会评估上一轮迭代计算中的权值和本轮迭代之后权值的差异，如果发现总体来说权值没有明显变化，说明系统已进入稳定状态，则可以结束计算。将页面根据Authority 权值得分由高到低排序，取权值最高的若干页面作为响应用户查询的搜索结果输出。如果比较发现两轮计算总体权值差异较大，则继续进入下一轮迭代计算，直到整个系统权值稳定为止。

 

 

 

 

HITS 算法存在的问题

HITS 算法整体而言是个效果很好的算法，目前不仅在搜索引擎领域应用，而且被自然语言处理及社交分析等很多其他计算机领域借鉴使用，并取得了很好的应用效果。尽管如此，最初版本的HITS 算法仍然存在一些问题，而后续很多基于HITS 算法的链接分析方法，也是立足于改进HITS 算法存在的这些问题而提出的。

归纳起来，HITS 算法主要在以下几个方面存在不足。

计算效率较低

因为HITS 算法是与查询相关的算法，所以必须在接收到用户查询后实时进行计算，而HITS 算法本身需要进行很多轮迭代计算才能获得最终结果，这导致其计算效率较低，这是实际应用时必须慎重考虑的问题。

主题漂移问题

如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么使用 HITS 算法很可能会给予这些无关网页很高的排名，导致搜索结果发生主题漂移，这种现象被称为紧密链接社区现象（Tightly-Knit Community Effect）。

易被作弊者操纵结果

HITS 算法从机制上很容易被作弊者操纵，比如作弊者可以建立一个网页，页面内容增加很多指向高质量网页或者著名网站的网址，这就是一个很好的Hub 页面，之后作弊者再将这个网页链接指向作弊网页，于是可以提升作弊网页的Authority 得分。

结构不稳定

所谓结构不稳定，就是说在原有的扩展网页集合内，如果添加删除个别网页或者改变少数链接关系，则HITS 算法的排名结果就会有非常大的改变。

HITS 算法与PageRank 算法比较

HITS算法和PageRank 算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出，两者无论是在基本概念模型，还是计算思路及技术实现细节都有很大的不同，下面对两者之间的差异进行逐一说明。

· HITS 算法是与用户输入的查询请求密切相关的，而PageRank 与查询请求无关。所以，HITS 算法可以单独作为相似性计算评价标准，而PageRank 必须结合内容相似性计算才可以用来对网页相关性进行评价。

· HITS 算法因为与用户查询密切相关，所以必须在接收到用户查询后进行实时计算，计算效率较低；而PageRank 则可以在爬虫抓取完成后离线计算，在线直接使用计算结果，计算效率较高。

· HITS 算法的计算对象数量较少，只需计算扩展集合内网页之间的链接关系；而PageRank 是全局性算法，对所有互联网页面节点进行处理。

· 从两者的计算效率和处理对象集合大小来比较，PageRank 更适合部署在服务器端，而HITS 算法更适合部署在客户端。

· HITS 算法存在主题泛化问题，所以更适合处理具体的用户查询；而PageRank 算法在处理宽泛的用户查询时更有优势。

· HITS 算法在计算时，对于每个页面需要计算两个分值，而PageRank 算法只需计算一个分值即可；在搜索引擎领域，更重视HITS 算法计算出的Authority 权值，但是在很多应用HITS 算法的其他领域，Hub 分值也有很重要的作用。

· 从链接反作弊的角度来说，PageRank 从机制上优于HITS 算法，而HITS 算法更易遭受链接作弊的影响。

· HITS 算法结构不稳定，当对扩展网页集合内链接关系做出很小改变，则对最终排名有很大影响；而PageRank 算法相对HITS 而言表现稳定，其根本原因在于PageRank 计算时的远程跳转。

 

 

——本段文字节选自《这就是搜索引擎：核心技术详解》

本书详细信息:http://blog.chinaunix.net/space.php?uid=13164110&do=blog&id=3054077