概述
标签传播算法(LPA, Label Propagation Algorithm)是基于标签传播的社区识别算法,是以标签分布达到稳定为目标的一种对点进行聚类的迭代过程。该算法的结果具有一定的随机性,但由于时间复杂度低,且无需事先指定社区数量,适用于大型复杂网络,并且常被包含在学术界和工业界的基准测试里。
算法的相关资料如下:
- U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks (2007)
基本概念
标签
标签是指定的节点某一的属性值。标签可以向其所在节点的有标签的一步邻居传播,有标签的节点可以选取来自其一步邻居的标签。在进行社区划分时,标签代表节点所属的社区,标签传播意味着社区范围扩张。
考虑上图中红色节点标签 a
和黄色节点标签 b
的传播:
- 蓝色节点是这两个节点的共同邻居,它将根据
a
、b
两个标签的权重决定选取哪个标签,或者在允许的情况下二者都选取; - 红色节点有自环边,因此标签
a
也会向它自身传播; - 绿色节点不是黄色节点的一步邻居,因此标签
b
无法在一轮传播中传播到绿色节点;如果紫色节点(绿色节点的唯一邻居)选取了标签b
,该标签在下一轮传播时能传播到绿色节点。
Ultipa 的 LPA 支持全量标签传播,即所有初始标签均有效可传播。如需指定部分标签有效,请联系 Ultipa 技术团队进行算法定制。
标签占比
如果规定节点每次只能选取邻居节点的一个标签,则为单一标签传播;如果允许同时选取多个标签,则为多标签传播。
多标签传播中,一个节点选取了多个标签后,每个标签将获得与其权重成正比的占比,同时一个节点的所有标签占比和为 1。对于单一标签传播,每个节点只有唯一标签且占比为 1。
例如,某节点选取了一个标签,则该标签的占比为 1
;某节点选取了两个标签 a
和 b
,权重分别为 1.5
和 1
,则 a
和 b
的占比分别为 1.5/(1.5+1) = 0.6
和 1/(1.5+1) = 0.4
。
标签权重
节点 j
的标签 l
向其邻居节点 i
传播时的权重等于 l
在 j
的占比、j
的权重、i
与 j
之间的边权重和这三者的乘积;当 i
有多个邻居节点拥有标签 l
时,需要对来自所有邻居节点的标签 l
权重求和:
上式中,p(l)
为 l
在 j
的占比,w(j)
为 j
的权重,A(ij)
为 i
、j
之间的边权重和。
需指定点的某个数值类属性作为点权重,指定边的某个数值类属性作为边权重。
标签选取
节点标签选取的原则是从邻居标签中选取权重最高的一个或多个标签作为该节点的新标签,并为每个新标签计算占比。当标签的权重排名出现并列情况且影响到标签的选择时,从并列的标签中随机选取。
对于图中任意节点 i
,l
为 i
的邻居的标签,w(l)
为 l
的权重,则 i
的新标签 l'
可表示为:
如前所述,对于多标签传播的情况,算法将对点的标签权重进行归一化处理,即将每个标签权重转化为标签占比。
算法开始时,根据算法的参数设置给节点初始化标签;在每轮迭代中,为每个节点计算是否能从其邻居标签中选取出和现有标签不一样的标签;计算完所有节点后,对能选出新标签的点进行标签更新。按此规则循环迭代直至没有点能选出新标签,或迭代轮数达到限制。
Ultipa 的 LPA 在更新节点标签时遵循同步更新原则,对于由此可能产生的标签震荡情况(多见于二分图中),算法有相应的中断机制。
特殊处理
孤点、不连通图
对于不连通图,各孤点、连通分量之间没有邻边,不能相互传递标签,不含有相同初始标签的连通分量不会被划分为相同社区。
自环边
LPA 对自环边的处理与节点度算法 algo(degree)
相同,都是每条自环边计算两次。
有向边
对于有向边,LPA 会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的图为例,节点和边的权重均为 1,节点内的字母是初始标签,节点 16 没有初始标签,运行 LPA,迭代 5 次:
算法结果 1:每个点最多保留一个标签,返回 _uuid
、label_1
、probability_1
三列
_uuid | label_1 | probability_1 |
---|---|---|
1 | C | 1.000000 |
2 | C | 1.000000 |
3 | C | 1.000000 |
4 | C | 1.000000 |
5 | C | 1.000000 |
6 | H | 1.000000 |
7 | H | 1.000000 |
8 | H | 1.000000 |
9 | H | 1.000000 |
10 | H | 1.000000 |
11 | N | 1.000000 |
12 | N | 1.000000 |
13 | N | 1.000000 |
14 | N | 1.000000 |
15 | O | 1.000000 |
16 |
算法统计值 1:标签数量 label_count
label_count |
---|
4 |
算法结果 2:每个点最多保留两个标签,返回 _uuid
、label_1
、probability_1
、label_2
、probability_2
五列
_uuid | label_1 | probability_1 | label_2 | probability_2 |
---|---|---|---|---|
1 | C | 0.705578 | A | 0.294422 |
2 | C | 0.658854 | A | 0.341145 |
3 | A | 0.508263 | C | 0.491737 |
4 | C | 0.688864 | E | 0.311136 |
5 | A | 0.572178 | C | 0.427822 |
6 | H | 0.723903 | A | 0.276097 |
7 | H | 0.797693 | I | 0.202307 |
8 | H | 0.645654 | I | 0.354346 |
9 | H | 0.779780 | A | 0.220220 |
10 | H | 0.617815 | I | 0.382185 |
11 | N | 0.611782 | M | 0.388218 |
12 | N | 0.611782 | M | 0.388218 |
13 | N | 0.766861 | M | 0.233139 |
14 | N | 0.663694 | M | 0.336306 |
15 | O | 1.000000 | ||
16 |
算法统计值 2:标签数量 label_count
label_count |
---|
8 |
命令和参数配置
- 命令:
algo(lpa)
params()
参数配置项如下:
名称 | 类型 | 默认值 |
规范 |
描述 |
---|---|---|---|---|
node_label_property | @<schema>.<property> |
/ | 数值或字符串类的点属性,需LTE | 作为标签的 schema 及属性名称;无该属性的点不参与计算;忽略时使用随机数作为节点的标签 |
node_weight_property | @<schema>.<property> |
/ | 数值类的点属性,需LTE | 点权重所在的 schema 及属性名称;无该属性的点不参与计算;忽略表示权重为 1 |
edge_weight_property | @<schema>.<property> |
/ | 数值类的边属性,需LTE | 边权重所在的 schema 及属性名称;无该属性的边不参与计算;忽略表示权重为 1 |
k | int | 1 | >=1 | 最多为每个点保留的标签数量;标签按照占比排列 |
loop_num | int | 5 | >= 1 | 算法迭代轮数 |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留两个标签,迭代 5 次
algo(lpa).params({
node_label_property: @default.name,
k: 2,
loop_num: 5
}) as a,b return a,b
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 |
---|---|
filename | _id ,label_1 ,probability_1 ,...label_k ,probability_k |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留两个标签,迭代 5 次,将算法结果回写至名为 lpa 的文件
algo(lpa).params({
node_label_property: @default.name,
k: 2,
loop_num: 5
}).write({
file:{
filename: "lpa"
}
})
2. 属性回写
配置项 |
回写内容 | 类型 |
数据类型 |
---|---|---|---|
property | label_1 , probability_1 , ... label_k , probability_k |
点属性 | 标签的数据类型为 string ,标签占比的数据类型为 float |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留两个标签,迭代 5 次,将算法结果分别回写至名为 newName_1、probability_1、newName_2、probability_2 的点属性
algo(lpa).params({
node_label_property: @default.name,
k: 2,
loop_num: 5
}).write({
db:{
property: "newName"
}
})
3. 统计回写
统计项名称 | 数据类型 | 描述 |
---|---|---|
label_count |
int | 标签个数 |
标签个数是指算法结束时,图中剩余标签的个数;当 k = 1 时,由于每个节点只保留一个标签,因此标签个数即为社区个数。
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留两个标签,迭代 5 次,将算法统计值回写至任务信息
algo(lpa).params({
node_label_property: @default.name,
k: 2,
loop_num: 5
}).write()
直接返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其各标签、标签占比 | _uuid , label_1 , probability_1 , ... label_k , probability_k |
1 | KV | 标签个数 | label_count |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留一个标签,迭代 5 次,将算法结果和统计值分别定义为别名 results 和 count 并返回
algo(lpa).params({
node_label_property: @default.name,
k: 1
}) as results, count
return results, count
流式返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其各标签、标签占比 | _uuid , label_1 , probability_1 , ... label_k , probability_k |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留一个标签,迭代 5 次,返回结果并按照标签名称和点的 UUID 升序排列
algo(lpa).params({
node_label_property: @default.name,
k: 1,
loop_num: 5
}).stream() as lpa
return lpa order by lpa.label_1, lpa._uuid
实时统计
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | KV | 标签个数 | label_count |
示例:运行 LPA,标签所在属性为 @default.name,最多为每个节点保留一个标签,迭代 5 次,返回社区数量
algo(lpa).params({
node_label_property: @default.name,
k: 1,
loop_num: 5
}).stats() as count
return count
结果一致性
受节点顺序、同权重标签随机选取、并行计算等因素的影响,标签传播算法的社区划分结果可能会不同。