HITS算法

Hyperlink-Induced Topic Search，简称HITS算法，是一种由Jon Kleinberg开发的对网页进行评分排名的链路分析算法。

网络的枢纽性和权威性源于互联网最初形成时候对网页创建的观察，即某些网页，被称之为网络枢纽，作为大型目录，它们所持有的信息实际上并不具有权威性，而是作为一个广泛的信息目录的汇总中心，引导用户直接访问其他具有权威性的网页。换句话说，一个好的枢纽表示一个网页可以链接网页，一个具有权威性的网页会被很多枢纽中心指向。

发展历史

学术期刊上

对学术期刊进行排名有许多的方法。其中有一个方法叫做Garfield的影响因子。像《Science》和《Nature》这样的期刊被引用的次数很多，所以这些杂志具有很高的影响因子。因此，如果比较两种被引用次数大致相同的期刊，但其中一种被《Science》和《Nature》杂志引用次数较多的，则该期刊的排名会更高。换句话说，被一个影响因子更高的文章引用比被影响因子更低的文章引用更好。

万维网上

这种现象同样发生在互联网上。通过计算一个网页的链接数量，我们可以大致估计出它在网络上的排名，但是如果这些链接中有两个来自雅虎、谷歌或者 MSN 等网站的主页，那么一个只有很少的链接的网页也可能有较高的排名。因为这些网站都是影响因子更高的，而且都是搜索引擎，因此网页的排名可以比其实际高得多。

算法描述

根集展开为基本集

HITS算法的基本思想就是：每个网页的重要性由两个指标刻画——权威性 Authority和枢纽性 Hub 。例如当我们想要查找“集智俱乐部”有关的页面时候，显然集智俱乐部首页最具有权威性。但是，如果万维网上有一个网页H，该网页的功能就是给出全世界所有科技类的组织机构的主页链接，那么其中就会包含有集智俱乐部。那么H网页就会有较高的枢纽值，也就是说网页H可以链接到一些比较有权威性质的网站。

在HITS算法中，第一步是检索与关键字最相关的页面。得到的结果集合为根集 root set，即该集合可以通过基于文本的搜索算法获得。根集展开为基本集 base set。基本集则由一个网页指向的其他网页和其他指向该网页的网页组成。基本集中的网页以及这些页面之间的所有超链接形成一个重点突出的子图。HITS计算仅在此聚焦子图上执行。据Kleinberg的结论，建立基础集的原因是要确保网页的绝对权威性。

权威性和枢纽性是互相依存、互相影响的。权威值是指所有导入链接所在的页面中枢纽值之和。枢纽值指的是网页上所有导出链接指向页面的权威值之和。实际应用中，还需要考虑链接页面的相关性。

该算法执行一系列迭代过程，每个迭代包含两个基本步骤：

权威值更新：更新每个节点的权威值，使其等于指向每个节点的枢纽值的总和。即通过从被识别为信息的的页面链接到一个节点，该节点将获得较高的权威值。
枢纽值更新：更新每个节点的枢纽值分数，使其等于它指向的每个节点的权威值之和。即通过链接到被认为是该主题的权威值的节点，节点被赋予较高的枢纽值。

节点的权威值和枢纽值使用以下算法计算：

从每个节点的中心得分和权限得分为1开始。
权威值更新
枢纽值更新
通过将每个Hub得分除以所有Hub得分的平方和的平方根，然后将每个Authority得分除以所有Authority得分的平方和的平方根来归一化值。
根据需要从第二步重复。

像拉里·佩奇 Larry Page和谢尔盖·布林 Sergey Brin的PageRank，HITS 是一种基于Web上文档链接的迭代算法。但是它确实有一些主要区别：

它取决于查询，也就是说，链接分析产生的（枢纽值和权威值）受搜索词的影响；
作为推论，它是在查询时而不是在索引时执行的，同时伴随着查询时处理的性能下降。
搜索引擎通常不使用它。
它计算每个文档的两个分数，即枢纽值和权威值，而不是一个PageRank。
它是在“相关”文档的一小部分（“聚焦子图”或基本集）上处理的，而不是像PageRank那样处理所有文档。

计算

算法开始，每一个网页p的初始值为让权威值[math]\displaystyle{ auth(p) = 1 }[/math]，枢纽值[math]\displaystyle{ hub(p) = 1 }[/math]。每一次计算的时候都需要考虑两个值的更新，即权威值更新和枢纽值更新。为了计算每个网页节点的"枢纽值/权威值"得分，使用权威值更新规则和枢纽值更新规则进行反复迭代。

权威值更新规则

对于每个网页 p，[math]\displaystyle{ auth (p) }[/math]更新为[math]\displaystyle{ auth(p) = \sum_{q\in P_{t_{0}}}hub(q) }[/math] 其中，[math]\displaystyle{ P_{t_{0}} }[/math]是所有链接到网页p的网页，即权威值更新为所有导入链接所在的页面中枢纽值求和。

枢纽值更新规则

对于每个网页p，更新[math]\displaystyle{ hub(p) }[/math]：

[math]\displaystyle{ hub(p) = \sum_{q\in P_{from}}auth(q) }[/math]

其中[math]\displaystyle{ P_{t_{from}} }[/math]是所有指向网页p的网页。即枢纽值更新为网页p上所有导出链接指向网页的权威值求和。

归一化

在反复迭代后，确定节点的最终权威-枢纽值分数。由于直接按照两者的更新规则进行迭代会导致值出现偏差，因此有必要在每次迭代后进行归一化。因此，最后获得的值将最终收敛。

算法流程

(1)初始化：设定网络中的所有节点的权威值和枢纽值[math]\displaystyle{ x_{i_{0}}, y_{i{0}} }[/math],其中[math]\displaystyle{ i=0,1,2,...,N }[/math]。

(2)迭代过程：在第k步（k>=1)进行如下三种操作：

a.权威值校正规则：每一个节点的权威值正为指向它的节点的枢纽值之和，即：

[math]\displaystyle{ x^{'}_{i}(k) = \sum^{N}_{j=1}a_{ji}y_{j}(k-1),i = 1,2,...,N }[/math]。

b.枢纽值校正规则：每一个节点的枢纽值校正为它所指向的节点的权威值之和，即：

[math]\displaystyle{ y^{'}_{i}(k) = \sum^{N}_{j=1}a_{ji}x_{j}(k-1),i = 1,2,...,N }[/math]。

c.归一化：

[math]\displaystyle{ x_{i}(k)= \frac{x^{'}_{i}(k)}{||x^{'}(k)||},y_{i}(k)= \frac{y^{'}_{i}(k)}{||y^{'}(k)||},i=1,2,...,N }[/math]

伪代码

G := set of pages
for each page p in G do
    p.auth = 1 // p.auth is the authority score of the page p
    p.hub = 1 // p.hub is the hub score of the page p
    for step from 1 to k do // run the algorithm for k steps
        norm = 0
        for each page p in G do  // update all authority values first
            p.auth = 0
            for each page q in p.incomingNeighbors do // p.incomingNeighbors is the set of pages that link to p
                p.auth += q.hub
            norm += square(p.auth) // calculate the sum of the squared auth values to normalise
         norm = sqrt(norm)
         for each page p in G do  // update the auth scores 
             p.auth = p.auth / norm  // normalise the auth values
         norm = 0
         for each page p in G do  // then update all hub values
             p.hub = 0
             for each page r in p.outgoingNeighbors do // p.outgoingNeighbors is the set of pages that p links to
                 p.hub += r.auth
             norm += square(p.hub) // calculate the sum of the squared hub values to normalise
         norm = sqrt(norm)
         for each page p in G do  // then update all hub values
             p.hub = p.hub / norm   // normalise the hub values

编者推荐

书籍《网络科学导论》封面

网络科学导论

对各种复杂网络的定量与定性特征的科学理解已成为网络时代科学研究中一个极其重要的挑战性课题，网络科学就是一门正在兴起的面对这一挑战的交叉性学科。本书致力于系统地介绍网络科学的基本概念、思想和方法，使得具有高等数学基础的读者都能够看懂，并具备把网络科学方法用于实际网络分析的能力。为此，本书没有过多地陷入数学和物理推导，而是更为关注网络科学的思维习惯和研究方式。本书在概要介绍了网络科学的背景和研究意义之后，分为四个部分详细介绍了网络基本概念、网络拓扑性质、网络拓扑模型和网络动力学。

HITS算法--从原理到实现

该文章介绍HITS算法的HITS算法的来源、原理，并利用python和MapReduce实现该算法。

本中文词条由ZQ用户参与编译，Meng莫薄荷编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。