✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

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 order by rank.authority desc

结果：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)