概述

HITS（Hyperlink-Induced Topic Search，超链接诱导的主题搜索）算法由L.M. Kleinberg于1999年提出，旨在提高万维网（WWW）搜索方法的质量。HITS利用“权威”和“枢纽”之间的相互增强关系来评估一组相连的实体并进行排名。

• L.M. Kleinberg, Authoritative Sources in a Hyperlinked Environment (1999)

基本概念

权威和枢纽

在WWW环境，网页间的超链接代表一种潜在的认可：网页A的创建者在网页A中包含指向网页B的链接，在某种程度上赋予了网页B一定的权威。因此可以认为，入度很大的节点是权威（Authority）。

如果一个节点指向相当多数量的权威节点，这个节点就称为枢纽（Hub）。

如下图所示，红色节点可被视为好的权威，绿色节点可被视为好的枢纽。

枢纽和权威节点之间存在一种相互增强、相辅相成的关系：一个好的枢纽意味着它指向许多好的权威，一个好的权威又会被许多好的枢纽所指向。

计算权威和枢纽

HITS算法在全图上迭代运行，通过链路结构计算每个节点的权威权值（表示为x）和枢纽权值（表示为y）。具有较大x值和y值的节点分别被视为更好的权威和枢纽。

在有向图G=(V, E)中，所有节点的x和y初始值都设为1。在每一轮迭代中，对于每个节点p∈V，根据下式更新其x和y值：

以下是一个例子：

每轮迭代结束时，分别将各点的x和y值进行归一化处理并保持：

算法在所有节点的x和y变化值小于规定的收敛偏差（tolerance）时停止，若迭代轮数达到限制，算法也会结束。原作者在实验中发现，算法收敛地相当快，通常迭代20次就足够了。

特殊说明

• HITS算法不考虑自环边。
• 没有入边的节点的权威权值为0，没有出边的节点的枢纽权值为0。

语法

• 命令：algo(hits_centrality)
• 参数：

示例

示例图如下：

文件回写

algo(hits_centrality).params({}).write({
  file: {
    filename: 'rank'
  }
})

结果：文件rank

H,0.000000,0.000000
G,0.213196,0.190701
F,0.426420,0.000000
E,0.000000,0.476726
D,0.000000,0.572083
C,0.000000,0.476726
B,0.213196,0.381382
A,0.852796,0.190701

属性回写

algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).write({
  db: {
    authority: 'auth',
    hub: 'hub'
  }
})

结果：每个节点的权威权值回写至名为auth的点属性下，每个节点的枢纽权值回写至名为hub的点属性下

直接返回

algo(hits_centrality).params() as rank
return rank

结果：rank

流式返回

algo(hits_centrality).params({
  max_loop_num: 20,
  tolerance: 0.0001
}).stream() as rank
find().nodes({_uuid == rank._uuid}) as nodes
order by rank.hub desc
return table(nodes._id, rank.hub)

结果：table(nodes._id, rank.hub)