HITS算法

超文本敏感标题搜索（HITS）是由Jon Kleinberg开发的一种链接分析算法，用于评估网页。

我们现在制定一个计划，在给定查询的情况下，为每个网页分配两个分数。一个被称为其中枢纽值（Hub Scores），另一个被称为权威值(Authority Scores)。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值是指所有导入链接所在的页面中枢纽之和。对于任何查询，我们根据返回的分数生成两个有序列表，一个列表的排名根据枢纽值，而另一个则是根据权威值。

这种方法源于对网页创建的特殊洞察，即有两种主要类型的网页可用作广泛主题搜索（broad-topic searches）的结果。通过广泛的主题搜索，例如我们希望进行诸如“我希望了解白血病”的信息查询。这些主题下有包含权威信息的页面——在这种情况下，国家癌症研究所关于白血病的网页将是这样一个页面——我们在搜索结果中展示这些页面，在我们将要描述的计算中，它们是将以高权威值出现的页面。

另一方面，Web上有许多页面是手动编译的关于特定主题的权威网页的链接列表。这些枢纽页面（hub pages）本身并不是某特定主题的权威信息来源，而是对该主题感兴趣的汇编人员对信息进行了总结。我们将采用的方法是使用这些枢纽页面来发现权威页面，在我们将要描述的计算中，这些中心页面将会得到高枢纽值。

一个好的枢纽页面指向许多有效的权威机构，而一个良好的权威页面是许多好的枢纽页面指向的页面。因此，我们似乎对枢纽和当局有了一个循环的定义；我们将把它变成一个迭代计算。假设我们有一个包含良好枢纽页面和权威页面的网络子集，以及它们之间的超链，我们将迭代计算该子集中每个网页的枢纽值和权威值。

对于我们网站子集中的网页$ v $，我们使用$ h（v）$来表示它的枢纽值和$ a（v）$表示它的权威值。最初，我们为所有节点$ v $设置$ h（v）= a（v）= 1 $。我们还用$ v \ mapsto $（v|--->y）来表示从$ v $到$ y $的超链接的存在。迭代算法的核心是根据以下方程对给出的所有页面的枢纽值和权威值进行的同时更新，它表达了良好的枢纽页面指向良好的权威页面和良好的权威页面是被好的枢纽页面所指向的直观概念。

因此，上式的第一行将页面$ v $的枢纽值设置为它链接到的页面的权威分数的总和。 换句话说，如果$ v $链接到拥有高权威分数的页面，它的枢纽值就会增加。 第二行扮演相反的角色; 如果页面$ v $拥有良好的枢纽值，则其权威分数会增加。

当我们迭代执行这些更新时，会发生什么情况，重新计算枢纽值，然后基于重新计算的枢纽值得出新的权威分数等等？ 让我们将上式重写为矩阵 - 矢量形式。 让$ \ vec {h} $和$ \ vec {a} $分别表示我们的网络子集中的所有枢纽和所有权威评分的向量。 令$ A $表示我们正在处理的Web图的子集的邻接矩阵：$ A $是一个方形矩阵，子集中的每个页面都有一行一列。 如果存在从页面$ i $到页面$ j $的超链接，则条目$ A_ {ij} $为1，否则为0。 然后，我们可以重新表达上式：

其中$ A ^ T $表示矩阵$ A $的转置。 现在上述等式的每一行的右侧是等式的另一行的左侧的向量。将这些彼此代入，我们可以将等式重写为：

现在，可以看出上述方程与一对特征向量方程有着惊人的相似性; 事实上，如果我们用$ = $符号替换$ \ leftarrow $符号并引入（未知）特征值，则上述方程的第一行成为$ AA ^ T $的特征向量的方程，而第二行成为 $ A ^ TA $的特征向量，即：

这里我们用$ \ lambda_h $来表示$ AA ^ T $的特征值和$ \ lambda_a $来表示$ A ^ TA $的特征值。

由此我们可以推导出HITS算法是的一些关键想法：

1. 通过适当的特征值缩放，则上述等式中的迭代更新可以等同于用于计算$ AA ^ T $和$ A ^ TA $的特征向量的乘方迭代方法（power iteration method）。
2. 在计算这些特征向量条目时，我们不限于使用乘方迭代方法; 实际上，我们可以使用任何快速方法来计算随机矩阵的主特征向量。

由此得出的计算采用以下形式：

1. 提取网页的目标子集，形成由其超链接形成的图并计算$ AA ^ T $和$ A ^ TA $。
2. 计算$ AA ^ T $和$ A ^ TA $的主要特征向量以形成枢纽值$ \ vec {h} $和权威分数$ \ vec {a} $的向量。
3. 输出得分最高枢纽值和最高权威值。

【描述来源：Manning, C. D.; Raghavan, P. and Schütze, H.(2008). Introduction to Information Retrieval, Cambridge University Press.】

发展历史

HITS 算法是由康奈尔大学( Cornell University ) 的Jon Kleinberg 博士于1997 年首先提出的,为IBM 公司阿尔马登研究中心( IBM Almaden Research Center) 的名为“CLEVER”的研究项目中的一部分。

由于超链接分析算法显着提高了搜索结果在Web上的相关性，以至于所有主要的Web搜索引擎都声称使用某种类型的超链接分析。 然而，搜索引擎并没有透露他们执行的超链接分析类型的细节。 Henzinger讨论了如何将超链接分析应用于排名算法，并调查网络搜索引擎可以使用此分析的其他方式。

2002年，Flake等学者将超链接分析算法的应用范围扩展。因为Web社区是网页的集合，其中每个成员页面在社区内的超链接比在社区外有更多的超链接，可以概括这个定义来识别具有不同尺寸和水平的凝聚力的社区。

2008年，Sun和Bai指出，交易数据库可以表示为二部图，因此HITS可以应用于交易数据库的分析。 他们提出一种新的度量w-support，它不需要预先指定的权重。 它使用基于链接的模型来考虑交易的质量。 论文中给出了一种快速挖掘算法，并给出了大量的实验结果。

主要事件

发展分析

瓶颈

HITS是查询相关（query dependent）的，也就是说，链接分析产生的两个分数受搜索条件的影响。另外，由于HITS是迭代算法，其计算效率较低。此外，HITS可能会出现紧密链接社区现象（Tightly-Knit Community Effect），即当页面集合中包含无关页面且互相指向，HITS算法很可能会给予这些无关网页很高的排名。HITS还很容易被作弊者恶意操纵，比如作弊者可以创建一个包含很多权威页面的枢纽页面，再将该页面指向自己的页面，提高权威分数。

未来发展方向

HITS目前不仅是搜索引擎领域的基础算法，还被自然语言处理以及社交分析等研究领域人员借鉴使用，其背后的逻辑简单有效，仍然是一种十分重要的算法。

Contributor：Yuanyuan Li