概述
标签传播算法(LPA, Label Propagation Algorithm)是一种基于标签传播的社区识别算法。每个节点初始化标签后,在算法的每次迭代中,每个节点都会将其标签更新为在其邻居中最普遍的标签。这个迭代过程会使连接密集的节点拥有同一标签,有相同标签的节点继而形成一个社区。
LPA不要求预先设定要划分的社区数量,也不将任何用于衡量社区划分优劣的标准作为目标,相反,它仅利用网络结构来引导其进程,这使得LPA能够有效地在大型和复杂的网络中运行。
算法的相关资料如下:
- U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks (2007)
基本概念
标签
指定的一个属性值或UUID对节点标签进行初始化。算法结束时,拥有相同标签的节点属于同一社区。
在LPA中,所有的初始标签都是有效的,即能够进行传播。如果需要将某些标签指定为无效,请联系嬴图团队定制算法。
标签传播
在最简单的场景中,每次迭代传播时,每个节点都会将其标签更新为其最多邻居拥有的标签。
如下例所示,蓝色节点的标签将从d
更新为c
。
![](https://img.ultipa.cn/draw/draw_d7f7a10b38974c9ea9559b8b3c22294b.jpg?v='1684995025103')
考虑节点和边权重时,标签权重则等于相应节点和边权重的乘积之和,每个节点将其标签更新为权重最大的那一个。
以下的示例中包含节点和边的权重,蓝色节点的标签将从d
更新为a
。
![](https://img.ultipa.cn/draw/draw_91e2068e11f54dd18a03da297d8100b9.jpg?v='1684994974827')
多标签传播
在多标签传播中,每个节点在传播过程中会保留多个标签。在这种情况下,节点的每个标签会关联一个与其权重成正比的标签概率,而每个节点的标签概率总和保持为1。
在下面的示例中,每个节点保留2个标签,其概率写在标签旁,蓝色节点的标签将从d, c
更新为a, c
,标签概率为Pa = 6.3/(6.3+1.85) = 0.77和Pc = 1.85/(6.3+1.85) = 0.23。
![](https://img.ultipa.cn/draw/draw_0a57771d2de34c95a730ba7f48016dad.jpg?v='1685005342870')
特殊说明
- LPA忽略边的方向,按照无向边进行计算。
- 具有自环边的节点能将自身当前的标签传播给自身,并且每条自环边计算两次。
- LPA在更新节点标签时遵循同步更新原则,即所有节点会根据其邻居的标签同时更新其标签。但在某些情况下可能会发生标签振荡,这多见于二分图中。为了解决这个问题,LPA包含一个中断机制,可以检测并防止标签过度振荡。
- 受节点顺序、同权重标签的随机选取以及并行计算等因素的影响,标签传播算法的社区划分结果可能会不同。
语法
- 命令:
algo(lpa)
- 参数:
名称 | 类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
node_label_property | @<schema>?.<property> |
数值/字符串类型,需LTE | / | 是 | 用于初始化节点标签的点属性,无该属性的点不参与标签传播;不设置时使用节点的UUID作为标签 |
node_weight_property | @<schema>?.<property> |
数值类型,需LTE | / | 是 | 作为节点权重的点属性 |
edge_weight_property | @<schema>?.<property> |
数值类型,需LTE | / | 是 | 作为边权重的边属性 |
loop_num | int | ≥1 | 5 |
是 | 传播的迭代次数 |
k | int | ≥1 | 1 |
是 | 最多为每个节点保留的标签数量(按照标签概率从大到小排序) |
示例
示例图如下,节点的Schema为user,边的Schema为connect,属性@connect.strength的值已标注在图中:
![](https://img.ultipa.cn/draw/draw_52d99aad60004860a2c848c9c5b87c4c.jpg?v='1685001250173')
文件回写
配置项 |
回写内容 |
---|---|
filename | _id ,label_1 ,probability_1 ,...label_k ,probability_k |
algo(lpa).params({
k: 2,
loop_num: 5,
edge_weight_property: 'strength'
}).write({
file:{
filename: "lpa"
}
})
统计值:label_count = 7
结果:文件lpa
O,1,0.599162,2,0.400838,
N,1,0.634582,2,0.365418,
M,1,0.610834,2,0.389166,
L,1,0.607434,2,0.392566,
K,1,0.619842,2,0.380158,
J,14,0.655975,8,0.344025,
I,14,0.546347,8,0.453653,
H,9,0.690423,7,0.309577,
G,14,0.569427,8,0.430573,
F,9,0.784132,7,0.215869,
E,9,0.519003,12,0.480997,
D,14,0.781072,9,0.218928,
C,12,0.540345,9,0.459655,
B,9,0.559427,14,0.440573,
A,14,0.768171,12,0.231829,
属性回写
配置项 |
回写内容 | 类型 |
数据类型 |
---|---|---|---|
property | label_1 , probability_1 , ... label_k , probability_k |
点属性 | 标签:string ,标签概率:float |
algo(lpa).params({
node_label_property: 'interest',
edge_weight_property: '@connect.strength',
k: 2,
loop_num: 10
}).write({
db:{
property: "lab"
}
})
统计值:label_count = 5
结果:每个节点的标签和对应的概率分别回写至名为lab_1、probability_1、lab_2和probability_2的点属性下
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其各标签、标签占比 | _uuid , label_1 , probability_1 , ... label_k , probability_k |
1 | KV | 标签个数 | label_count |
algo(lpa).params({
node_label_property: '@user.interest',
node_weight_property: '@user.level'
}) as res
return res
结果:res
_uuid | label_1 | probability_1 |
---|---|---|
15 | novel | 1.000000 |
14 | swimming | 1.000000 |
13 | novel | 1.000000 |
12 | novel | 1.000000 |
11 | novel | 1.000000 |
10 | violin | 1.000000 |
9 | badminton | 1.000000 |
8 | piano | 1.000000 |
7 | badminton | 1.000000 |
6 | badminton | 1.000000 |
5 | piano | 1.000000 |
4 | piano | 1.000000 |
3 | piano | 1.000000 |
2 | piano | 1.000000 |
1 | piano | 1.000000 |
algo(lpa).params({
node_label_property: 'interest',
k: 2
}) as res, stats
return res, stats
结果:res和stats
_uuid | label_1 | probability_1 | label_2 | probability_2 |
---|---|---|---|---|
15 | novel | 0.642453 | saxophone | 0.357547 |
14 | swimming | 0.577773 | saxophone | 0.422227 |
13 | novel | 0.610180 | swimming | 0.389820 |
12 | saxophone | 0.608193 | novel | 0.391807 |
11 | piano | 0.536380 | saxophone | 0.463620 |
10 | piano | 0.588276 | movie | 0.411724 |
9 | piano | 0.595449 | movie | 0.404551 |
8 | piano | 0.637065 | movie | 0.362935 |
7 | piano | 0.554655 | movie | 0.445345 |
6 | piano | 0.720096 | movie | 0.279904 |
5 | piano | 0.502892 | flute | 0.497108 |
4 | piano | 0.648339 | flute | 0.351661 |
3 | piano | 0.520442 | flute | 0.479558 |
2 | piano | 0.624170 | flute | 0.375831 |
1 | piano | 0.670773 | flute | 0.329227 |
label_count |
---|
6 |
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其各标签、标签占比 | _uuid , label_1 , probability_1 , ... label_k , probability_k |
algo(lpa).params({
node_label_property: '@user.interest',
node_weight_property: '@user.level',
edge_weight_property: 'strength',
loop_num: 10
}).stream() as lpa
group by lpa.label_1
with count(lpa) as labelCount
return table(lpa.label_1, labelCount)
order by labelCount desc
结果:table(lpa.label_1, labelCount)
lpa.label_1 | labelCount |
---|---|
piano | 5 |
swimming | 3 |
violin | 2 |
novel | 2 |
tennis | 2 |
统计返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | KV | 标签个数 | label_count |
algo(lpa).params({
node_label_property: 'interest',
edge_weight_property: 'strength',
k: 1,
loop_num: 5
}).stats() as count
return count
结果:count
label_count |
---|
5 |