概述

标签传播算法（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。

考虑节点和边权重时，标签权重则等于相应节点和边权重的乘积之和，每个节点将其标签更新为权重最大的那一个。

以下的示例中包含节点和边的权重，蓝色节点的标签将从d更新为a。

多标签传播

在多标签传播中，每个节点在传播过程中会保留多个标签。在这种情况下，节点的每个标签会关联一个与其权重成正比的标签概率，而每个节点的标签概率总和保持为1。

在下面的示例中，每个节点保留2个标签，其概率写在标签旁，蓝色节点的标签将从d, c更新为a, c，标签概率为P_a = 6.3/(6.3+1.85) = 0.77和P_c = 1.85/(6.3+1.85) = 0.23。

特殊说明

• LPA忽略边的方向，按照无向边进行计算。
• 具有自环边的节点能将自身当前的标签传播给自身，并且每条自环边计算两次。
• LPA在更新节点标签时遵循同步更新原则，即所有节点会根据其邻居的标签同时更新其标签。但在某些情况下可能会发生标签振荡，这多见于二分图中。为了解决这个问题，LPA包含一个中断机制，可以检测并防止标签过度振荡。
• 受节点顺序、同权重标签的随机选取以及并行计算等因素的影响，标签传播算法的社区划分结果可能会不同。

语法

• 命令：algo(lpa)
• 参数：

示例

示例图如下，节点的Schema为user，边的Schema为connect，属性@connect.strength的值已标注在图中：

文件回写

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,

属性回写

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的点属性下

直接返回

algo(lpa).params({
  node_label_property: '@user.interest',
  node_weight_property: '@user.level'
}) as res
return res

结果：res

algo(lpa).params({
  node_label_property: 'interest',
  k: 2
}) as res, stats
return res, stats

结果：res和stats

流式返回

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)

统计返回

algo(lpa).params({
  node_label_property: 'interest',
  edge_weight_property: 'strength',
  k: 1,
  loop_num: 5
}).stats() as count 
return count

结果：count