|
|
# 050 | 经典图算法之HITS
|
|
|
|
|
|
这周我们分享的内容是如何理解网页和网页之间的关系。周一我们介绍了用图（Graph）来表达网页与网页之间的关系并计算网页的重要性，就是经典算法PageRank。今天我来介绍一下PageRank的姊妹算法：**HITS算法**。
|
|
|
|
|
|
## HITS的简要历史
|
|
|
|
|
|
HITS是Hypertext-Induced Topic Search算法的简称。这个算法是由康奈尔大学计算机科学教授乔·克莱恩堡（Jon Kleinberg）于1998年发明的，正好和我们周一讲的布林和佩奇发表PageRank算法是同一年。
|
|
|
|
|
|
这里有必要简单介绍一下乔这个人。乔于1971年出生在马萨诸塞州波士顿。1993年他毕业于康奈尔大学获得计算机科学学士学位，并于1996年从麻省理工大学获得计算机博士学位。1998的时候，乔正在位于美国西海岸硅谷地区的IBM阿尔玛登（Almaden）研究院做博士后研究。HITS的工作最早发表于1998年在旧金山举办的第九届ACM-SIAM离散算法年会上（详细论述可参阅参考文献）。
|
|
|
|
|
|
乔目前是美国国家工程院（National Academy of Engineering）和美国自然与人文科学院（American Academy of Arts and Sciences）院士。顺便提一下，乔的弟弟罗伯特·克莱恩堡也在康奈尔大学计算机系任教职。
|
|
|
|
|
|
## HITS的基本原理
|
|
|
|
|
|
在介绍HITS算法的基本原理之前，我们首先来复习一下网页的网络结构。每一个网页都有一个“输出链接”（Outlink）的集合。输出链接指的是从当前网页出发所指向的其他页面，比如从页面A有一个链接到页面B，那么B就是A的输出链接。根据这个定义，我们来看“输入链接”（Inlink），指的就是指向当前页面的其他页面，比如页面C指向页面A，那么C就是A的输入链接。
|
|
|
|
|
|
要理解HITS算法，我们还需要引入一组概念：**“权威”（Authority）结点**和**“枢纽”（Hub）结点**。这两类结点到底是什么意思呢？
|
|
|
|
|
|
HITS给出了一种“循环”的定义：**好的“权威”结点是很多“枢纽”结点的输出链接，好的“枢纽”结点则指向很多好的“权威”结点**。这种循环定义我们在PageRank的定义中已经见识过了。
|
|
|
|
|
|
很明显，要用数学的方法来表述权威结点和枢纽结点之间的关系就必须要为每一个页面准备两个值。因为从直觉上来说，不可能有一个页面完全是权威，也不可能有一个页面完全是枢纽。绝大多数页面都在这两种角色中转换，或者说同时扮演这两类角色。
|
|
|
|
|
|
数学上，对于每一个页面I，**我们用X来表达这个页面的“权威值”，用Y来表达这个页面的“枢纽值”**。那么，一个最直观的定义，对于I的权威值X来说，它是所有I页面的输入链接的枢纽值的总和。同理，I的枢纽值是所有I页面输出链接的权威值的总和。这就是HITS算法的原始定义。
|
|
|
|
|
|
我们可以看到，如果I页面的输入链接的枢纽值大，说明I页面经常被一些好的“枢纽”结点链接到，那么I自身的权威性自然也就增加了。反之，如果I能够经常指向好的“权威”结点，那I自身的“枢纽”性质也就显得重要了。
|
|
|
|
|
|
当然，和PageRank值一样，X和Y在HITS算法里也都是事先不可知的。因此，**HITS算法的重点就是要求解X和Y**。如果把所有页面的X和Y都表达成向量的形式，那么HITS算法可以写成X是矩阵L的转置和Y的乘积，而Y是矩阵L和X的乘积，这里的矩阵L就是一个邻接矩阵，每一行列表达某两个页面是否相连。进行一下代数变形，我们就可以得到X其实是一个矩阵A乘以X，这里的A是L的转置乘以L。Y其实是一个矩阵B乘以Y，这里的B是L乘以L的转置。
|
|
|
|
|
|
于是，惊人的一点出现了，那就是HITS算法其实是需要求解矩阵A或者矩阵B的主特征向量，也就是特征值最大所对应的特征向量，用于求解X或者Y。这一点和PageRank用矩阵表达的形式不谋而和。也就是说，尽管PageRank和HITS在思路和概念上完全不同，并且在最初的定义式上南辕北辙，但是经过一番变形之后，我们能够把两者都划归为**某种形式的矩阵求解特征向量的问题**。
|
|
|
|
|
|
实际上，**把图表达为矩阵，并且通过特征向量对图的一些特性进行分析是图算法中的一个重要分支**（当然，我们这里说的主要是最大的值对应的特征向量，还有其他的特征向量也有含义）。既然我们已经知道了需要计算最大的特征向量，那么之前计算PageRank所使用的“乘幂法”（Power Method）在这里也是可以使用的，我们在这里就不展开了。
|
|
|
|
|
|
如何把HITS算法用于搜索中呢？最开始提出HITS的时候是这么使用的。
|
|
|
|
|
|
**首先，我们根据某个查询关键字构建一个“相邻图”**（Neighborhood Graph）。这个图包括所有和这个查询关键字相关的页面。这里，我们可以简化为所有包含查询关键字的页面。这一步在现代搜索引擎中通过“倒排索引”（Inverted Index）就可以很容易地得到。
|
|
|
|
|
|
**有了这个相邻图以后，我们根据这个图建立邻接矩阵，然后就可以通过邻接矩阵计算这些结点的权威值和枢纽值**。当计算出这两组值之后，我们就可以根据这两组值给用户展现两种网页排序的结果，分别是根据不同的假设。
|
|
|
|
|
|
值得注意的是，PageRank是“查询关键字无关”（Query-Independent）的算法，也就是说每个页面的PageRank值并不随着查询关键字的不同而产生不同。而HITS算法是“查询关键字相关”（Query-Dependent）的算法。从这一点来说，HITS就和PageRank有本质的不同。
|
|
|
|
|
|
## HITS算法的一些特点
|
|
|
|
|
|
HITS算法依靠这种迭代的方法来计算权威值和枢纽值，你一定很好奇，这样的计算究竟收敛吗？是不是也需要像PageRank一样来进行特别的处理呢？
|
|
|
|
|
|
**答案是HITS一定是收敛的**。这点比原始的PageRank情况要好。然而，HITS在原始的情况下，不一定收敛到唯一一组权威值和枢纽值，也就是说，解是不唯一的。因此，我们其实需要对HITS进行一部分类似于PageRank的处理，那就是让HITS的邻接矩阵里面所有的结点都能够达到其他任何结点，只是以比较小的概率。经过这样修改，HITS就能够收敛到唯一的权威值和枢纽值了。
|
|
|
|
|
|
**HITS算法的好处是为用户提供了一种全新的视角，对于同一个查询关键字，HITS提供的权威排序和枢纽排序能够帮助用户理解自己的需求**。
|
|
|
|
|
|
当然，**HITS的弱点也来自于这个依赖于查询关键字的问题**。如果把所有的计算都留在用户输入查询关键字以后，并且需要在响应时间内计算出所有的权威值和枢纽值然后进行排序，这里面的计算量是很大的。所以，后来有研究者开始使用全局的网页图，提前来计算所有页面的权威值和枢纽值，然而这样做就失去了对某一个关键字的相关信息。
|
|
|
|
|
|
## 小结
|
|
|
|
|
|
今天我为你讲了HITS算法的核心思想 。 一起来回顾下要点：第一，我们讲了HITS的一些简明历史。第二，我们讲了HITS最原始的定义和算法，并且联系PageRank，讲了两者的异同之处。第三，我们分析了HITS的一些特点。
|
|
|
|
|
|
最后，给你留一个思考题，有没有办法把权威值和枢纽值所对应的两个排序合并成为一个排序呢？
|
|
|
|
|
|
欢迎你给我留言，和我一起讨论。
|
|
|
|
|
|
**参考文献**
|
|
|
|
|
|
1. Jon M. Kleinberg. _Authoritative sources in a hyperlinked environment_. J. ACM 46, 5 (September 1999), 604-632，1999.
|
|
|
|
|
|
**论文链接**
|
|
|
|
|
|
* [Authoritative sources in a hyperlinked environment](http://www.woodmann.com/searchlores/library/authoratitativesources.pdf)
|
|
|
|