“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

今天分享网络科学领域里面HITS算法这一主题。同为网络算法，HITS算法比较与PageRank算法有什么不同呢？本文将介绍HITS的基本概念，有哪些好玩的案例，知名的研究者、一些入门的学习资源。

一、HITS算法的起源

二、HITS算法的原理

三、HITS、PageRank算法的区别

四、知名学者推介

五、相关资源推介

六、集智百科词条志愿者招募

一、HITS算法的起源

HITS算法的全称是“基于超链接的主题搜索”(Hyperlink-Induced Topic Search)。该算法于1999年由Jon Kleinberg提出，是一种用于对网页进行排序的算法。网页排序之后的结果有助于人们更方便地得到所关注的信息。

图1：HITS算法示意图

HITS算法受学术期刊排名方法的启发。顶级期刊（如Science）被引用的次数很多，具有很高的影响因子，具有更高的权威性。故而在比较某两个被引用次数大致相同的期刊时，被顶级期刊引用次数多的那个排名会更高。

HITS算法和PageRank算法在原理上有些类似。都既考虑网页本身的链接数，也考虑所链接网页的权威性。不过它们在概念模型、计算思路以及技术实现细节上有不同之处。

二、HITS算法的原理

权威值与枢纽值

HITS算法的基本思想是：每个网页的重要性由两个指标刻画，权威值（Authority）与枢纽值（Hub）。一个权威值高的网页会被很多网页指向（如微博大V）。一个枢纽值高的网页会指向很多网页（如大型目录网页），见下图。

图2：评价重要性的两个指标：权威值 Authority 与枢纽值 Hub

举例来说，当我们查找与“集智俱乐部”有关的网页时，集智俱乐部的首页具有较高的权威值，因为相关网页都会指向首页。另一方面，当某个网页指向大量权威机构首页时，那么该网页就会有较高的枢纽值。

权威值和枢纽值是互相依存、互相影响的，它们的计算方式如下：

某网页的权威值 = 所有指向它的网页的枢纽值之和。

某网页的枢纽值 = 所有它指向网页的权威值之和。

根集合与基本集合

HITS算法并非在互联网中所有的网页上计算，而是只关注一小部分网页。该算法首先通过文本搜索找到与关键词最相关的页面，得到根集合（root set）。然后从根集合延展，找到与其直接相连的网页（即邻居），得到基本集合（base set）。根集合与基本集合构成一个子图，即HITS算法的输入网页。

图3：HITS算法的输入网页

算法流程：

1. 初始化：将各节点的权威值和枢纽值均设为1。

2. 更新节点的权威值

3. 更新节点的枢纽值

4. 将权威值和枢纽值归一化。

5. 重复2-4步骤，直至最终收敛。

三、HITS、PageRank算法的区别

HITS算法和PageRank算法可以看作兄弟算法。因为他们是同时期提出的对网页进行排序的两种算法。并且他们的原理有相似之处，都考虑了权威性网站的作用。

图4：PageRank算法示意

但这两种算法也有区别：

HITS计算每个网页的权威值和枢纽值，将二者分开考虑。而PageRank只计算PageRank值。
HITS只处理与关键词相关的网页集合，范围很小。而PageRank是全局算法，会计算互联网中所有网页的PageRank值。
因为上一点的缘故，HITS算法更适合部署在客户端，而PageRank更适合部署在服务器端。

四、知名学者简介

Jon Kleinberg

图5：Jon Kleinberg

美国计算机科学家，康奈尔大学计算机科学教授。2006年获得国际数学联盟颁发的内万林纳奖。Kleinberg的研究跨越了从计算机网络由到数据挖掘到生物分子结构比对等诸多领域。他最为人称道的成就是“小世界理论”和万维网搜索算法。他设计了HITS算法，该算法的相关研究工作启发了Google的PageRank算法的诞生。