概述
资源分配(Resource Allocation)算法基于一个假设,即节点通过它们共同的邻居作为传输者来相互传递资源。在其基本形式中,我们假设每个传输者拥有一个单位的资源,这个资源均匀分布给它的所有邻居。因此,两个节点之间的相似度可以通过一个节点向另一个节点传输的资源量来衡量。这个概念由Tao Zhou、Linyuan Lü和Yi-Cheng Zhang在2009年提出:
- T. Zhou, L. Lü, Y. Zhang, Predicting Missing Links via Local Information (2009)
它的计算公式如下:
![](https://img.ultipa.cn/2022-08-10-09-56-21-RA.jpg)
其中,N(u)是与节点u相连的节点集合。对于两个节点的每个共同邻居u,资源分配首先计算其度数|N(u)|的倒数,然后将所有共同邻居的这些倒数值相加。
计算图集中节点的度时:
- 如果两点间存在多条边,只计数一次;
- 不计算自环边。
资源分配分值较高表示节点间的相似度较大,分值为0则表示两个节点间没有相似性。
![](https://img.ultipa.cn/draw/draw_b86689aa4f2e4c5598dd981e0958996c.jpg?v='1691984801387')
在上图中,N(D) ∩ N(E) = {B, F},则RA(D,E) = + = + = 0.5833。
特殊说明
- 资源分配算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(topological_link_prediction)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 否 | 待计算的第一组节点的ID/UUID;算法将ids /uuids 中的每个节点与ids2 /uuids2 中的每个节点配对进行计算 |
ids2 / uuids2 | []_id / []_uuid |
/ | / | 否 | 待计算的第二组节点的ID/UUID;算法将ids /uuids 中的每个节点与ids2 /uuids2 中的每个节点配对进行计算 |
type | string | Resource_Allocation |
Adamic_Adar |
否 | 相似度衡量指标;计算资源分配时,保持此项为Resource_Allocation |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_4852484853184e96bd5e861849ccc940.jpg?v='1691985028310')
文件回写
配置项 | 回写内容 |
---|---|
filename | node1 ,node2 ,num |
algo(topological_link_prediction).params({
uuids: [3],
uuids2: [1,5,7],
type: 'Resource_Allocation'
}).write({
file:{
filename: 'ra'
}
})
结果:文件ra
C,A,0.250000
C,E,0.500000
C,G,0.333333
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNodePair | 点对及相似度 | node1 , node2 , num |
algo(topological_link_prediction).params({
ids: 'C',
ids2: ['A','C','E','G'],
type: 'Resource_Allocation'
}) as ra
return ra
结果:ra
node1 | node2 | num |
---|---|---|
3 | 1 | 0.25 |
3 | 5 | 0.5 |
3 | 7 | 0.333333333333333 |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNodePair | 点对及相似度 | node1 , node2 , num |
find().nodes() as n
with collect(n._id) as nID
algo(topological_link_prediction).params({
ids: 'C',
ids2: nID,
type: 'Resource_Allocation'
}).stream() as ra
where ra.num >= 0.3
return ra
结果:ra
node1 | node2 | num |
---|---|---|
3 | 4 | 0.583333333333333 |
3 | 5 | 0.5 |
3 | 7 | 0.333333333333333 |