HDC
概述
资源分配（Resource Allocation）算法基于一个假设，即节点通过它们共同的邻居作为传输者来相互传递资源。在其基本形式中，我们假设每个传输者拥有一个单位的资源，这个资源均匀分布给它的所有邻居。因此，两个节点之间的相似度可以通过一个节点向另一个节点传输的资源量来衡量。这个概念由Tao Zhou、Linyuan Lü和Yi-Cheng Zhang在2009年提出：
- T. Zhou, L. Lü, Y. Zhang, Predicting Missing Links via Local Information (2009)
它的计算公式如下：
其中，N(u)是与节点u相连的节点集合。对于两个节点的每个共同邻居u，资源分配首先计算其度数|N(u)|的倒数，然后将所有共同邻居的这些倒数值相加。
计算图集中节点的度时：
- 如果两点间存在多条边，只计数一次；
- 不计算自环边。
资源分配分值较高表示节点间的相似度较大，分值为0则表示两个节点间没有相似性。
在上图中，N(D) ∩ N(E) = {B, F}，则RA(D,E) = + = + = 0.5833。
特殊说明
- 资源分配算法忽略边的方向，按照无向边进行计算。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"A"}, {_id:"B"}, {_id:"C"}, {_id:"D"}, {_id:"E"}, {_id:"F"}, {_id:"G"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"B", _to:"E"}, {_from:"C", _to:"B"}, {_from:"C", _to:"D"}, {_from:"C", _to:"F"}, {_from:"D", _to:"B"}, {_from:"D", _to:"E"}, {_from:"F", _to:"D"}, {_from:"F", _to:"G"}])
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_tlp：
CALL hdc.graph.create("hdc-server-1", "hdc_tlp", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_tlp", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：topological_link_prediction
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
ids |
[]_id |
/ | / | 否 | 通过_id指定参与计算的第一组点；若未设置则计算所有点 |
uuids |
[]_uuid |
/ | / | 否 | 通过_uuid指定参与计算的第一组点；若未设置则计算所有点 |
ids2 |
[]_id |
/ | / | 否 | 通过_id指定参与计算的第二组点；若未设置则计算所有点 |
uuids2 |
[]_uuid |
/ | / | 否 | 通过_uuid指定参与计算的第二组点；若未设置则计算所有点 |
type |
String | Resource_Allocation |
Adamic_Adar |
否 | 指定待计算的相似度类型；计算资源分配时，设置为Resource_Allocation |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
文件回写
CALL algo.topological_link_prediction.write("hdc_tlp", {
params: {
ids: ["C"],
ids2: ["A","E","G"],
type: "Resource_Allocation",
return_id_uuid: "id"
},
return_params: {
file: {
filename: "ra.txt"
}
}
})
algo(topological_link_prediction).params({
project: "hdc_tlp",
ids: ["C"],
ids2: ["A","E","G"],
type: "Resource_Allocation",
return_id_uuid: "id"
}).write({
file: {
filename: "ra.txt"
}
})
结果：
_id1,_id2,result
C,A,0.25
C,E,0.5
C,G,0.333333
完整返回
CALL algo.topological_link_prediction("hdc_tlp", {
params: {
ids: ["C"],
ids2: ["A","C","E","G"],
type: "Resource_Allocation",
return_id_uuid: "id"
},
return_params: {}
}) YIELD ra
RETURN ra
exec{
algo(topological_link_prediction).params({
ids: ["C"],
ids2: ["A","C","E","G"],
type: "Resource_Allocation",
return_id_uuid: "id"
}) as ra
return ra
} on hdc_tlp
结果：
| _id1 | _id2 | result |
|---|---|---|
| C | A | 0.25 |
| C | E | 0.5 |
| C | G | 0.333333 |
流式返回
MATCH (n)
RETURN collect_list(n._id) AS IdList
NEXT
CALL algo.topological_link_prediction("hdc_tlp", {
params: {
ids: ["C"],
ids2: IdList,
type: "Resource_Allocation",
return_id_uuid: "id"
},
return_params: {
stream: {}
}
}) YIELD ra
FILTER ra.result >= 0.3
RETURN ra
find().nodes() as n
with collect(n._id) as IdList
exec{
algo(topological_link_prediction).params({
ids: ["C"],
ids2: IdList,
type: "Resource_Allocation",
return_id_uuid: "id"
}).stream() as ra
where ra.result >= 0.3
return ra
} on hdc_tlp
结果：
| _id1 | _id2 | result |
|---|---|---|
| C | D | 0.583333 |
| C | E | 0.5 |
| C | G | 0.333333 |