概述
HANP(Hop Attenuation & Node Preference,跳跃衰减和节点倾向性)算法在标签传播算法(LPA)的基础上引入了标签分值衰减机制,并考虑邻居节点的度对邻居标签权重的影响。HANP的目标是提高网络中社区检测的准确性和鲁棒性。该算法由Ian X.Y. Leung等人于2009年提出:
- I.X.Y. Leung, P. Hui, P. Liò, J. Crowcroft, Towards real-time community detection in large networks (2009)
基本概念
跳跃衰减
HANP算法赋予每个标签一个分值,该分值随着标签从其原点向远传播而逐渐降低。所有标签的初始分值均为1。当某节点从其邻域采用一个新标签时,新标签在该节点上的分值会在原分值基础上减去一个跳跃衰减因子δ(0 < δ < 1)的大小。
跳跃衰减机制限制标签只向附近的节点传播,能防止某标签在网络中传播得太广从而形成过大的社区。
节点倾向性
在计算新的最大标签时,HANP包含基于节点度的倾向性。当节点j∈Ni将其标签L传播到节点i时,标签L的权重计算公式为:
![](https://img.ultipa.cn/img/2023-05-29-11-47-33-hanp1.jpg)
其中,
- sj(L)是标签L在节点j上的分值。
- degj是节点j的度。当m>0 时,倾向于度较大的节点;当m<0时,倾向于度较小的节点;当m=0 时,对节点度没有倾向性。
- wij是节点i和j之间所有边的权重和。
以下的示例中包含边权重,标签分值写在标签旁,设置m=2以及δ=0.2,蓝色节点的标签将从d
更新为a
,标签a
在蓝色节点上的分值衰减至0.6。
![](https://img.ultipa.cn/draw/draw_611cb47526b74a4db1b4c70a7040e6da.jpg?v='1685333790738')
特殊说明
- HANP忽略边的方向,按照无向边进行计算。
- 具有自环边的节点能将自身当前的标签传播给自身,并且每条自环边计算两次。
- 如果节点选择的标签与当前自身的标签一致,δ=0。
- HANP在更新节点标签时遵循同步更新原则,即所有节点会根据其邻居的标签同时更新其标签。由于引入了标签分值,HANP通常不会出现标签振荡。
- 受节点顺序、同权重标签的随机选取以及并行计算等因素的影响,HANP算法的社区划分结果可能会不同。
语法
- 命令:
algo(hanp)
- 参数:
名称 | 类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
node_label_property | @<schema>?.<property> |
数值/字符串类型,需LTE | / | 是 | 用于初始化节点标签的点属性,无该属性的点不参与标签传播;不设置时使用节点的UUID作为标签 |
edge_weight_property | @<schema>?.<property> |
数值类型,需LTE | / | 是 | 作为边权重的边属性 |
m | float | / | 0 |
是 | 邻居节点度的幂指数:m >0 时,倾向于度较大的节点;m <0 时,倾向于度较小的节点;m =0 时,对节点度没有倾向性 |
delta | float | [0,1] | 0 |
是 | 跳跃衰减因子δ |
loop_num | int | ≥1 | 5 |
是 | 传播的迭代次数 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下,节点的Schema为user,边的Schema为connect,属性@connect.strength的值已标注在图中:
![](https://img.ultipa.cn/draw/draw_4222e6cd40354580b5a075819c7cafe8.jpg?v='1685341505293')
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,label_1 ,score_1 |
algo(hanp).params({
loop_num: 10,
edge_weight_property: 'strength',
m: 2,
delta: 0.2
}).write({
file:{
filename: 'hanp'
}
})
统计值:label_count = 4
结果:文件hanp
O,13,-0.600000,
N,6,-1.000000,
M,6,-1.000000,
L,13,-0.600000,
K,13,-0.600000,
J,1,-0.200000,
I,1,-0.200000,
H,1,-0.200000,
G,1,-0.200000,
F,14,-1.000000,
E,6,-0.200000,
D,6,-0.200000,
C,6,-0.200000,
B,6,-0.200000,
A,6,-0.400000,
属性回写
配置项 |
回写内容 |
类型 |
数据类型 |
---|---|---|---|
property | label_1 ,score_1 |
点属性 | 标签:string ,标签分值:float |
algo(hanp).params({
node_label_property: '@user.interest',
m: 0.1,
delta: 0.3
}).write({
db:{
property: 'lab'
}
})
统计值:label_count = 3
结果:每个节点的标签和标签分值分别回写至名为lab_1和score_1的点属性下
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其标签、标签分值 | _uuid , label_1 , score_1 |
1 | KV | 标签个数 | label_count |
algo(hanp).params({
loop_num: 12,
node_label_property: '@user.interest',
m: 1,
delta: 0.2
}) as res, stats
return res, stats
结果:res和stats
_uuid | label_1 | score_1 |
---|---|---|
15 | movie | -1.400000 |
14 | movie | -0.400000 |
13 | saxophone | -0.200000 |
12 | saxophone | -0.200000 |
11 | saxophone | -0.400000 |
10 | flute | -0.200000 |
9 | flute | -0.200000 |
8 | flute | -0.200000 |
7 | flute | -0.200000 |
6 | movie | -0.400000 |
5 | movie | -0.200000 |
4 | movie | -0.200000 |
3 | movie | -0.200000 |
2 | movie | -0.200000 |
1 | movie | -0.400000 |
label_count |
---|
3 |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其标签、标签分值 | _uuid , label_1 , score_1 |
algo(hanp).params({
loop_num: 12,
node_label_property: '@user.interest',
m: 1,
delta: 0.2
}).stream() as hanp
group by hanp.label_1
with count(hanp) as labelCount
return table(hanp.label_1, labelCount)
order by labelCount desc
结果:table(hanp.label_1, labelCount)
hanp.label_1 | labelCount |
---|---|
movie | 8 |
flute | 4 |
saxophone | 3 |
统计返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | KV | 标签个数 | label_count |
algo(hanp).params({
loop_num: 5,
node_label_property: 'interest',
m: 0.6,
delta: 0.2
}).stats() as count
return count
结果:count
label_count |
---|
5 |