概述
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)。
如下图所示,红色节点可被视为好的权威,绿色节点可被视为好的枢纽。
![](https://img.ultipa.cn/draw/draw_2ed110856aed4603a573d6aeaa79610b.jpg?v='1672217278797')
枢纽和权威节点之间存在一种相互增强、相辅相成的关系:一个好的枢纽意味着它指向许多好的权威,一个好的权威又会被许多好的枢纽所指向。
计算权威和枢纽
HITS算法在全图上迭代运行,通过链路结构计算每个节点的权威权值(表示为x)和枢纽权值(表示为y)。具有较大x值和y值的节点分别被视为更好的权威和枢纽。
在有向图G=(V, E)中,所有节点的x和y初始值都设为1。在每一轮迭代中,对于每个节点p∈V,根据下式更新其x和y值:
![](https://img.ultipa.cn/img/2023-02-01-18-01-37-xy.jpg)
以下是一个例子:
![](https://img.ultipa.cn/draw/draw_43b88a2290b64a76ac72baf583da2007.jpg?v='1680058951390')
每轮迭代结束时,分别将各点的x和y值进行归一化处理并保持:
![](https://img.ultipa.cn/img/2023-03-29-11-11-42-norm.jpg)
算法在所有节点的x和y变化值小于规定的收敛偏差(tolerance)时停止,若迭代轮数达到限制,算法也会结束。原作者在实验中发现,算法收敛地相当快,通常迭代20次就足够了。
特殊说明
- HITS算法不考虑自环边。
- 没有入边的节点的权威权值为0,没有出边的节点的枢纽权值为0。
语法
- 命令:
algo(hits_centrality)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
max_loop_num | int | >=1 | 20 |
是 | 最大迭代轮数;运行至规定的最大轮数后,即使没达到收敛要求,算法也会停止 |
tolerance | float | (0,1) | 0.001 |
是 | 收敛偏差;某轮迭代后,如果所有点的权威权值和枢纽权值的总变化值小于收敛偏差,算法结束 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_533f96d36b594838b20d4ff9666bd730.jpg?v='1680581848708')
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,authority ,hub |
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
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
authority | authority |
点属性 | double |
hub | hub |
点属性 | double |
algo(hits_centrality).params({
max_loop_num: 20,
tolerance: 0.0001
}).write({
db: {
authority: 'auth',
hub: 'hub'
}
})
结果:每个节点的权威权值回写至名为auth的点属性下,每个节点的枢纽权值回写至名为hub的点属性下
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其权威权值和枢纽权值 | _uuid , authority , hub |
algo(hits_centrality).params() as rank
return rank
结果:rank
_uuid | authority | hub |
---|---|---|
8 | 3.20199049138017e-11 | 0 |
7 | 0.213196444093741 | 0.190700611234451 |
6 | 0.426419530029166 | 1.43197368054726e-11 |
5 | 0 | 0.476726292571473 |
4 | 0 | 0.572082555485605 |
3 | 0 | 0.476726292571473 |
2 | 0.213196444093741 | 0.381381944251153 |
1 | 0.852795952652963 | 0.190700611234451 |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其权威权值和枢纽权值 | _uuid , authority , hub |
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)
nodes._id | rank.hub |
---|---|
D | 0.572082555485605 |
E | 0.476726292571473 |
C | 0.476726292571473 |
B | 0.381381944251153 |
G | 0.190700611234451 |
A | 0.190700611234451 |
F | 1.43197368054726e-11 |
H | 0 |