标签传播

有向

无向

异构节点

异构关系

加权关系

术语表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点一视同仁，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系一视同仁，无论其类型如何。
加权关系: 加权特性。该算法支持使用关系属性作为权重，通过relationshipWeightProperty配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，忽略任何关系权重的值。

简介

标签传播算法 (LPA) 是一种用于在图中查找社区的快速算法。它仅以网络结构为指导来检测这些社区，并且不需要预定义的目标函数或关于社区的先验信息。

LPA 通过在整个网络中传播标签来工作，并根据这个标签传播过程形成社区。

该算法的直觉是，一个单一标签可以在密集连接的节点组中迅速占据主导地位，但在稀疏连接的区域将难以传播。标签将被困在密集连接的节点组内，当算法结束时，那些最终拥有相同标签的节点可以被认为是同一社区的一部分。

该算法工作原理如下

每个节点都用一个唯一的社区标签（一个标识符）进行初始化。
这些标签在网络中传播。
在传播的每次迭代中，每个节点都会将其标签更新为其邻居中最大数量所属的标签。平局会任意但确定性地打破。
当每个节点都拥有其邻居的多数标签时，LPA 达到收敛。
如果达到收敛或用户定义的最大迭代次数，LPA 将停止。

随着标签的传播，密集连接的节点组会迅速就一个唯一标签达成共识。在传播结束时，只有少数标签会保留下来——大多数会消失。在收敛时具有相同社区标签的节点被认为属于同一社区。

LPA 的一个有趣特性是，可以为节点分配预先标签，以缩小生成解决方案的范围。这意味着它可以作为一种半监督的方式来查找社区，我们可以手动选择一些初始社区。

有关此算法的更多信息，请参阅

运行此算法需要足够的内存。在运行此算法之前，我们建议您阅读内存估算。

语法

本节介绍在每种执行模式下执行标签传播算法所使用的语法。我们正在描述命名图语法的变体。要了解更多关于通用语法变体的信息，请参阅语法概述。

各模式下的标签传播语法

在命名图上以流模式运行标签传播。

CALL gds.labelPropagation.stream(
  graphName: String,
  configuration: Map
)
YIELD
    nodeId: Integer,
    communityId: Integer

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图筛选。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可提供的 ID，用于更轻松地跟踪算法进度。
logProgress	布尔值	`true`	是	如果禁用，将不会记录进度百分比。
maxIterations	整数	`10`	是	最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性的名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
seedProperty	字符串	`不适用`	是	定义初始数字标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	标记以决定组件标识符是否映射到连续的 ID 空间（需要额外内存）。
minCommunitySize	整数	`0`	是	仅返回社区大小大于或等于给定值的节点。
1. 在 GDS 会话中，默认值为可用处理器数量

表 3. 结果
名称	类型	描述
节点 ID	整数	节点 ID。
communityId	整数	社区 ID。

在命名图上以统计模式运行标签传播。

CALL gds.labelPropagation.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

表 4. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图筛选。

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可提供的 ID，用于更轻松地跟踪算法进度。
logProgress	布尔值	`true`	是	如果禁用，将不会记录进度百分比。
maxIterations	整数	`10`	是	最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性的名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
seedProperty	字符串	`不适用`	是	定义初始数字标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	标记以决定组件标识符是否映射到连续的 ID 空间（需要额外内存）。
2. 在 GDS 会话中，默认值为可用处理器数量

表 6. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
postProcessingMillis	整数	计算百分位数和社区计数所用的毫秒数。
communityCount	整数	找到的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签，则为 True。
communityDistribution	映射	包含社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。
configuration	映射	用于运行算法的配置。

在命名图上以变异模式运行标签传播。

CALL gds.labelPropagation.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

表 7. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图筛选。

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入社区 ID 的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签筛选命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型筛选命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可提供的 ID，用于更轻松地跟踪算法进度。
maxIterations	整数	`10`	是	最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性的名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
seedProperty	字符串	`不适用`	是	定义初始数字标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	标记以决定组件标识符是否映射到连续的 ID 空间（需要额外内存）。

表 9. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
mutateMillis	整数	向内存图添加属性所用的毫秒数。
postProcessingMillis	整数	计算百分位数和社区计数所用的毫秒数。
nodePropertiesWritten	整数	写入的节点属性数量。
communityCount	整数	找到的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签，则为 True。
communityDistribution	映射	包含社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。
configuration	映射	用于运行算法的配置。

在命名图上以写入模式运行标签传播。

CALL gds.labelPropagation.write(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityCount: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  communityDistribution: Map,
  configuration: Map

表 10. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图筛选。

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可提供的 ID，用于更轻松地跟踪算法进度。
logProgress	布尔值	`true`	是	如果禁用，将不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	写入社区 ID 的 Neo4j 数据库中的节点属性。
maxIterations	整数	`10`	是	最大迭代次数。
nodeWeightProperty	字符串	`null`	是	包含节点权重的节点属性的名称。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
seedProperty	字符串	`不适用`	是	定义初始数字标签的节点属性名称。
consecutiveIds	布尔值	`false`	是	标记以决定组件标识符是否映射到连续的 ID 空间（需要额外内存）。
minCommunitySize	整数	`0`	是	只有社区大小大于或等于给定值的社区 ID 才会写入 Neo4j。
3. 在 GDS 会话中，默认值为可用处理器数量

表 12. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据所用的毫秒数。
computeMillis	整数	运行算法所用的毫秒数。
writeMillis	整数	写回结果数据所用的毫秒数。
postProcessingMillis	整数	计算百分位数和社区计数所用的毫秒数。
nodePropertiesWritten	整数	写入的节点属性数量。
communityCount	整数	找到的社区数量。
ranIterations	整数	已执行的迭代次数。
didConverge	布尔值	如果算法在提供的最大迭代次数内收敛到稳定的标签，则为 True。
communityDistribution	映射	包含社区大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。
configuration	映射	用于运行算法的配置。

示例

以下所有示例都应在一个空数据库中运行。

这些示例通常使用Cypher 投影。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行标签传播算法的示例。目的是说明结果如何以及提供如何在实际设置中使用该算法的指南。我们将在一个由少量节点以特定模式连接的小型社交网络图上进行此操作。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (alice:User {name: 'Alice', posts: 4, seed_label: 52}),
  (bridget:User {name: 'Bridget', posts: 13, seed_label: 21}),
  (charles:User {name: 'Charles', posts: 55, seed_label: 43}),
  (doug:User {name: 'Doug', posts: 5, seed_label: 21}),
  (mark:User {name: 'Mark', posts: 7, seed_label: 19}),
  (michael:User {name: 'Michael', posts: 15, seed_label: 52}),

  (alice)-[:FOLLOW {weight: 1}]->(bridget),
  (alice)-[:FOLLOW {weight: 10}]->(charles),
  (mark)-[:FOLLOW {weight: 1}]->(doug),
  (bridget)-[:FOLLOW {weight: 1}]->(michael),
  (doug)-[:FOLLOW {weight: 1}]->(mark),
  (michael)-[:FOLLOW {weight: 1}]->(alice),
  (alice)-[:FOLLOW {weight: 1}]->(michael),
  (bridget)-[:FOLLOW {weight: 1}]->(alice),
  (michael)-[:FOLLOW {weight: 1}]->(bridget),
  (charles)-[:FOLLOW {weight: 1}]->(doug)

此图表示六个用户，其中一些相互关注。除了 name 属性外，每个用户还有一个 seed_label 属性。seed_label 属性表示图中用于为节点播种标签的值。例如，这可以是标签传播算法先前运行的结果。此外，每个关系都有一个权重属性。

以下语句将使用 Cypher 投影来投影图并将其以“myGraph”的名称存储在图目录中。

MATCH (source:User)-[r:FOLLOW]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {
    sourceNodeProperties: source { .posts, .seed_label },
    targetNodeProperties: target { .posts, .seed_label },
    relationshipProperties: r { .weight }
  }
)

在以下示例中，我们将演示在此图上使用标签传播算法。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 write 模式。估算算法有助于了解在图上运行算法对内存的影响。当您稍后实际在其中一种执行模式下运行算法时，系统将执行估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要了解更多信息，请参阅自动估算和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下将估算在写入模式下运行算法所需的内存

CALL gds.labelPropagation.write.estimate('myGraph', { writeProperty: 'community' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
节点数量	关系数量	最小字节数	最大字节数	所需内存
6	10	1592	1592	“1592 字节”

流

在 stream 执行模式下，算法返回每个节点的社区 ID。这允许我们直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。例如，我们可以对结果进行排序，以查看属于同一社区的节点并排显示。

有关 stream 模式的更多详细信息，请参阅流。

以下将运行算法并流式传输结果

CALL gds.labelPropagation.stream('myGraph')
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 14. 结果
名称	社区
“Alice”	0
“Bridget”	0
“Michael”	0
“Charles”	4
“Doug”	4
“Mark”	4

在上面的示例中，我们可以看到我们的图有两个社区，每个社区包含三个节点。算法的默认行为是运行 unweighted，即不使用节点或关系权重。weighted 选项将在加权中演示。

统计

在 stats 执行模式下，算法返回一行，其中包含算法结果的摘要。此执行模式没有任何副作用。通过检查 computeMillis 返回项，它可用于评估算法性能。在下面的示例中，我们将省略返回时间。该过程的完整签名可在语法部分中找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下将以 stats 模式运行算法

CALL gds.labelPropagation.stats('myGraph')
YIELD communityCount, ranIterations, didConverge

表 15. 结果
communityCount	ranIterations	didConverge
2	3	true

从上面的示例中我们可以看到，该算法找到了两个社区并在三次迭代中收敛。请注意，我们运行的是 unweighted 算法。

变异

mutate 执行模式在 stats 模式的基础上增加了一个重要的副作用：使用包含该节点社区 ID 的新节点属性更新命名图。新属性的名称使用强制配置参数 mutateProperty 指定。结果是与 stats 类似的单行摘要，但包含一些附加指标。当多个算法结合使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变异。

以下将运行算法并写回结果

CALL gds.labelPropagation.mutate('myGraph', { mutateProperty: 'community' })
YIELD communityCount, ranIterations, didConverge

表 16. 结果
communityCount	ranIterations	didConverge
2	3	true

返回的结果与 stats 示例中的相同。此外，图 'myGraph' 现在具有一个节点属性 community，用于存储每个节点的社区 ID。要了解如何检查内存图的新模式，请参阅列出图。

写入

write 执行模式在 stats 模式的基础上增加了一个重要的副作用：将每个节点的社区 ID 作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是与 stats 类似的单行摘要，但包含一些附加指标。write 模式允许将结果直接持久化到数据库。

有关 write 模式的更多详细信息，请参阅写入。

以下将运行算法并写回结果

CALL gds.labelPropagation.write('myGraph', { writeProperty: 'community' })
YIELD communityCount, ranIterations, didConverge

表 17. 结果
communityCount	ranIterations	didConverge
2	3	true

返回的结果与 stats 示例中的相同。此外，六个节点中的每个节点现在在 Neo4j 数据库中都有一个新属性 community，其中包含该节点的社区 ID。

加权

当我们投影 myGraph 时，我们也投影了关系属性 weight。为了让算法将此属性视为关系权重，我们必须将 relationshipWeightProperty 配置参数设置为 weight。

以下将在具有加权关系的图上运行算法并流式传输结果

CALL gds.labelPropagation.stream('myGraph', { relationshipWeightProperty: 'weight' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 18. 结果
名称	社区
“Bridget”	0
“Michael”	0
“Alice”	4
“Charles”	4
“Doug”	4
“Mark”	4

与算法的非加权运行相比，我们仍然有两个社区，但它们分别包含两个和四个节点。使用加权关系，节点 Alice 和 Charles 现在位于同一社区，因为它们之间存在强链接。

加权节点

通过 nodeWeightProperty 键指定节点权重，我们还可以控制节点社区对其邻居的影响。在计算特定社区的权重时，节点属性将乘以该节点关系的权重。

以下将在具有加权节点的图上运行算法并流式传输结果

CALL gds.labelPropagation.stream('myGraph', { nodeWeightProperty: 'posts' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 19. 结果
名称	社区
“Alice”	4
“Charles”	4
“Doug”	4
“Mark”	4
“Bridget”	5
“Michael”	5

我们已经使用 stream 模式来演示使用权重运行算法，所有算法模式都可使用这些配置参数。

种子社区

在算法计算开始时，每个节点都用一个唯一的标签初始化，并且标签在网络中传播。

可以通过设置 seedProperty 配置参数来提供一组初始标签。当我们投影 myGraph 时，我们也投影了节点属性 seed_label。我们可以使用此节点属性作为 seedProperty。

算法首先检查是否为节点分配了种子标签。如果没有种子标签，算法将为节点分配新的唯一标签。然后，使用这组初步标签，它在标签传播的每次迭代中，按顺序将每个节点的标签更新为新的标签，该标签是其邻居中最常见的标签。

consecutiveIds 配置选项不能与 seedProperty 结合使用，以保留种子值。

以下将使用预定义标签运行算法

CALL gds.labelPropagation.stream('myGraph', { seedProperty: 'seed_label' })
YIELD nodeId, communityId AS Community
RETURN gds.util.asNode(nodeId).name AS Name, Community
ORDER BY Community, Name

表 20. 结果
名称	社区
“Charles”	19
“Doug”	19
“Mark”	19
“Alice”	52
“Bridget”	52
“Michael”	52

如我们所见，社区是基于 seed_label 属性的，具体来说，19 来自节点 Mark，52 来自 Alice。

我们已经使用 stream 模式来演示使用 seedProperty 运行算法，此配置参数适用于算法的所有模式。