概述
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。
示例图集
创建示例图集:
// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}, {_id:"H"}])
insert().into(@default).edges([{_from:"C", _to:"A"}, {_from:"C", _to:"B"}, {_from:"B", _to:"A"}, {_from:"E", _to:"A"}, {_from:"E", _to:"G"}, {_from:"A", _to:"F"}, {_from:"D", _to:"A"}, {_from:"D", _to:"F"}, {_from:"F", _to:"H"}, {_from:"G", _to:"F"}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1
上,并命名为 hdc_hits
:
CALL hdc.graph.create("hdc-server-1", "hdc_hits", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_hits", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名:hits_centrality
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
---|---|---|---|---|---|
max_loop_num |
Integer | ≥1 | 20 |
是 | 最大迭代轮数。算法将在完成所有轮次后停止 |
tolerance |
Float | (0,1) | 0.001 |
是 | 某轮迭代后,若所有权威权值和枢纽权值的变化小于指定tolerance 时,表明结果已稳定,算法会停止 |
return_id_uuid |
String | uuid , id , both |
uuid |
是 | 在结果中使用_uuid 、_id 或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数;-1 返回所有结果 |
文件回写
CALL algo.hits_centrality.write("hdc_hits", {
params: {
return_id_uuid: "id"
},
return_params: {
file: {
filename: "ranks"
}
}
})
algo(hits_centrality).params({
return_id_uuid: "id",
project: "hdc_hits"
}).write({
file: {
filename: "ranks"
}
})
结果:
_id,authority,hub
D,0,0.572083
F,0.42642,1.43197e-11
H,3.20199e-11,0
B,0.213196,0.381382
A,0.852796,0.190701
E,0,0.476726
C,0,0.476726
G,0.213196,0.190701
数据库回写
将结果中的authority
值和hub
值写入指定点属性。两个属性类型均为double
。
CALL algo.hits_centrality.write("hdc_hits", {
params: {
max_loop_num: 20,
tolerance: 0.0001
},
return_params: {
db: {
authority: 'auth',
hub: 'hub'
}
}
})
algo(hits_centrality).params({
project: "hdc_hits",
max_loop_num: 20,
tolerance: 0.0001
}).write({
db: {
authority: 'auth',
hub: 'hub'
}
})
完整返回
CALL algo.hits_centrality("hdc_hits", {
params: {
return_id_uuid: "id"
},
return_params: {}
}) YIELD r
RETURN r
exec{
algo(hits_centrality).params({
return_id_uuid: "id"
}) as r
return r
} on hdc_hits
结果:
_id | authority | hub |
---|---|---|
D | 0 | 0.572083 |
F | 0.42642 | 0 |
H | 0 | 0 |
B | 0.213196 | 0.381382 |
A | 0.852796 | 0.190701 |
E | 0 | 0.476726 |
C | 0 | 0.476726 |
G | 0.213196 | 0.190701 |
流式返回
CALL algo.hits_centrality("hdc_hits", {
params: {
return_id_uuid: "id",
max_loop_num: 20,
tolerance: 0.0001
},
return_params: {
stream: {}
}
}) YIELD r
RETURN r._id, r.hub ORDER BY r.hub DESC
exec{
algo(hits_centrality).params({
return_id_uuid: "id",
max_loop_num: 20,
tolerance: 0.0001
}).stream() as r
return r._id, r.hub order by r.hub
} on hdc_hits
结果:
r._id | r.hub |
---|---|
D | 0.572083 |
E | 0.476726 |
C | 0.476726 |
B | 0.381382 |
A | 0.190701 |
G | 0.190701 |
F | 0 |
H | 0 |