概述
优先连接(Preferential Attachment)描述的是复杂网络中常见的“强者更强”现象,即拥有更多连接的节点更有可能建立新的连接。当两个节点都拥有大量的连接时,它们形成连接的概率显著增加。这一现象在2002年被A. Barabási和R. Albert用于他们提出的BA模型,该模型用于生成随机的无标度网络:
- R. Albert, A. Barabási, Statistical mechanics of complex networks (2001)
优先连接算法通过计算每个节点的邻居数的乘积来衡量两个节点之间的相似性。它的计算公式如下:
![](https://img.ultipa.cn/2022-08-10-09-24-26-PA.jpg)
其中,N(x)和N(y)分别是与节点x和节点y相连的节点集合。
优先连接分值较高表示节点间的相似度较大,分值为0则表示两个节点间没有相似性。
![](https://img.ultipa.cn/draw/draw_4b46a0b60fa141698093b656f3600ea2.jpg?v='1691983066684')
在上图中,PA(D,E) = |N(D)| * |N(E)| = |{B, C, E, F}| * |{B, D, F}| = 4 * 3 = 12。
特殊说明
- 优先连接算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
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 | Preferential_Attachment |
Adamic_Adar |
否 | 相似度衡量指标;计算优先连接时,保持此项为Preferential_Attachment |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下:
![](https://img.ultipa.cn/draw/draw_f0e1ac612f234b298d9ac04f1fa897ad.jpg?v='1691983348642')
文件回写
配置项 | 回写内容 |
---|---|
filename | node1 ,node2 ,num |
algo(topological_link_prediction).params({
uuids: [3],
uuids2: [1,5,7],
type: 'Preferential_Attachment'
}).write({
file:{
filename: 'pa'
}
})
结果:文件pa
C,A,3.000000
C,E,6.000000
C,G,3.000000
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNodePair | 点对及相似度 | node1 , node2 , num |
algo(topological_link_prediction).params({
ids: 'C',
ids2: ['A','C','E','G'],
type: 'Preferential_Attachment'
}) as pa
return pa
结果:pa
node1 | node2 | num |
---|---|---|
3 | 1 | 3 |
3 | 5 | 6 |
3 | 7 | 3 |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
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: 'Preferential_Attachment'
}).stream() as pa
where pa.num >= 2
return pa
结果:pa
node1 | node2 | num |
---|---|---|
3 | 2 | 12 |
3 | 4 | 12 |
3 | 5 | 6 |
3 | 6 | 9 |