弱连通分量 (Weakly Connected Components)

术语表

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

介绍

弱连通分量 (WCC) 算法用于查找有向图和无向图中的连通节点集。如果两个节点之间存在路径，则称它们是连通的。所有相互连通的节点集构成一个分量。与强连通分量 (SCC) 不同，WCC 不考虑节点间路径上关系的方向。例如，在有向图 (a)→(b) 中，即使没有 (b)→(a) 的有向关系，a 和 b 也将处于同一个分量中。

WCC 通常在分析初期使用，以了解图的结构。使用 WCC 理解图结构有助于在识别出的集群上独立运行其他算法。

该算法的实现基于以下论文

语法

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

各模式下的 WCC 语法

在命名图上以流模式 (stream mode) 运行 WCC。

CALL gds.wcc.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  componentId: Integer

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
分量 ID (componentId)	整数	分量 ID。

在命名图上以统计模式 (stats mode) 运行 WCC。

CALL gds.wcc.stats(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

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

表 6. 结果
名称	类型	描述
分量总数 (componentCount)	整数	计算出的分量数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计信息的毫秒数。
分量分布 (componentDistribution)	Map	包含分量大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位值的映射。
配置	Map	用于运行算法的配置。

在命名图上以变异模式 (mutate mode) 运行 WCC。

CALL gds.wcc.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入分量 ID 的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
seedProperty	字符串	`不适用`	是	用于设置节点的初始分量。属性值必须为数字。
阈值 (threshold)	浮点数	`null`	是	关系权重需高于此值才会被计入计算。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。

表 9. 结果
名称	类型	描述
分量总数 (componentCount)	整数	计算出的分量数量。
nodePropertiesWritten	整数	写入的节点属性数。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计信息的毫秒数。
分量分布 (componentDistribution)	Map	包含分量大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位值的映射。
配置	Map	用于运行算法的配置。

在命名图上以写入模式 (write mode) 运行 WCC。

CALL gds.wcc.write(
  graphName: String,
  configuration: Map
)
YIELD
  componentCount: Integer,
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

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

表 12. 结果
名称	类型	描述
分量总数 (componentCount)	整数	计算出的分量数量。
nodePropertiesWritten	整数	写入的节点属性数。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果写回 Neo4j 所用的毫秒数。
postProcessingMillis	整数	计算组件计数和分布统计信息的毫秒数。
分量分布 (componentDistribution)	Map	包含分量大小的最小值、最大值、平均值以及 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位值的映射。
配置	Map	用于运行算法的配置。

示例

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

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行弱连通分量算法的示例。其目的是说明结果的样子，并为在实际环境中使用该算法提供指南。我们将使用一个小型用户网络图，其中少数节点以特定模式连接。示例图如下所示

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

CREATE
  (nAlice:User {name: 'Alice'}),
  (nBridget:User {name: 'Bridget'}),
  (nCharles:User {name: 'Charles'}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK {weight: 0.5}]->(nBridget),
  (nAlice)-[:LINK {weight: 4}]->(nCharles),
  (nMark)-[:LINK {weight: 1.1}]->(nDoug),
  (nMark)-[:LINK {weight: 2}]->(nMichael);

该图有两个连通分量，每个分量有三个节点。连接每个分量中节点的关系具有一个 weight 属性，该属性决定了关系的强度。

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

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

在接下来的示例中，我们将演示如何在图上使用弱连通分量算法。

内存估算

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

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

以下内容将估算以写入模式运行算法所需的内存要求：

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

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	4	112	112	"112 字节"

流模式 (Stream)

在 stream 执行模式下，算法为每个节点返回分量 ID。这使我们能够直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。例如，我们可以对结果进行排序，以查看属于同一分量的节点排列在一起。

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

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

CALL gds.wcc.stream('myGraph')
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 14. 结果
名称 (name)	分量 ID (componentId)
"Alice"	0
“Bridget”	0
“Charles”	0
“Doug”	3
“Mark”	3
“Michael”	3

结果显示该算法识别出两个分量。这可以在示例图中进行验证。

算法的默认行为是运行 unweighted（无权重），即不使用 relationship 权重。weighted（加权）选项将在加权一节中演示。

实际的分量 ID 可能会有所不同，因为内存中图投影的节点顺序无法保证。在这种情况下，得到相反的解同样是可能的，例如，当我们的社区 0 节点被映射到社区 3，反之亦然。

统计模式 (Stats)

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

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

以下语句将以 stats 模式运行该算法：

CALL gds.wcc.stats('myGraph')
YIELD componentCount

表 15. 结果
分量总数 (componentCount)
2

结果显示 myGraph 有两个分量，这可以通过查看示例图来验证。

变异模式 (Mutate)

mutate 执行模式扩展了 stats 模式，并带有一个重要的副作用：更新命名图，为其添加一个包含该节点分量 ID 的新节点属性。新属性的名称由强制配置参数 mutateProperty 指定。结果是一个单行摘要，类似于 stats，但包含一些额外的指标。当结合使用多种算法时，mutate 模式特别有用。

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

以下语句将以 mutate 模式运行该算法：

CALL gds.wcc.mutate('myGraph', { mutateProperty: 'componentId' })
YIELD nodePropertiesWritten, componentCount;

表 16. 结果
nodePropertiesWritten	分量总数 (componentCount)
6	2

写入模式 (Write)

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个节点的分量 ID 作为属性写入 Neo4j 数据库。新属性的名称由强制配置参数 writeProperty 指定。结果是一个单行摘要，类似于 stats，但包含一些额外的指标。write 模式可以直接将结果持久化到数据库中。

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

以下语句将以 write 模式运行该算法：

CALL gds.wcc.write('myGraph', { writeProperty: 'componentId' })
YIELD nodePropertiesWritten, componentCount;

表 17. 结果
nodePropertiesWritten	分量总数 (componentCount)
6	2

从结果中可以看出，算法计算出相互连接的节点属于同一个连通分量。

加权 (Weighted)

通过配置算法使用权重，我们可以增加算法计算分量分配时的粒度。我们通过 relationshipWeightProperty 配置参数指定属性键来实现这一点。此外，我们可以为权重值指定一个阈值。这样，只有大于阈值权重的关系才会被算法考虑。我们通过 threshold 配置参数指定阈值。

如果关系没有指定的权重属性，算法将回退使用默认值零。

以下代码将使用关系权重运行算法并流式输出结果

CALL gds.wcc.stream('myGraph', {
  relationshipWeightProperty: 'weight',
  threshold: 1.0
}) YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS Name, componentId AS ComponentId
ORDER BY ComponentId, Name

表 18. 结果
名称	分量 ID (ComponentId)
`"Alice"`	`0`
`“Charles”`	`0`
`“Bridget”`	`1`
`“Doug”`	`3`
`“Mark”`	`3`
`“Michael”`	`3`

从结果中可以看出，名为 'Bridget' 的节点现在位于其自己的分量中，这是因为其关系权重小于配置的阈值，因此被忽略。

我们使用流模式来说明如何运行加权或无权重的算法，其他所有算法模式也都支持此配置参数。

种子分量 (Seeded components)

可以使用 seedProperty 配置参数为节点定义初步的分量 ID。如果我们想保留上一次运行的分量，并且确定没有因删除关系而拆分任何分量，这将非常有用。属性值必须为数字。

算法首先检查节点是否分配了种子分量 ID。如果有，则使用该分量 ID。否则，为该节点分配一个新的唯一分量 ID。

一旦每个节点都属于一个分量，算法就会合并连通节点的分量。当合并分量时，生成的分量始终是具有较小分量 ID 的那个。注意，consecutiveIds 配置选项不能与种子设定结合使用，以便保留种子值。

算法假设具有相同种子值的节点确实属于同一个分量。如果不同分量中的任意两个节点具有相同的种子，则其行为是不确定的。这种情况下建议在不使用种子的情况下运行 WCC。

为了在实践中演示这一点，我们将经过几个步骤

我们将运行算法并将结果写入 Neo4j。
然后我们将向图中添加另一个节点，该节点不会拥有步骤 1 中计算出的属性。
我们将投影一个新图，将步骤 1 的结果作为 nodeProperty
然后我们将再次以 stream 模式运行算法，并使用 seedProperty 配置参数。

我们将使用 WCC 的加权变体。

步骤 1

以下语句将以 write 模式运行该算法：

CALL gds.wcc.write('myGraph', {
  writeProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
})
YIELD nodePropertiesWritten, componentCount;

表 19. 结果
nodePropertiesWritten	分量总数 (componentCount)
6	3

步骤 2

在算法完成向 Neo4j 写入后，我们要在数据库中创建一个新节点。

以下代码将在 Neo4j 图中创建一个新节点，且没有分量 ID

MATCH (b:User {name: 'Bridget'})
CREATE (b)-[:LINK {weight: 2.0}]->(new:User {name: 'Mats'})

步骤 3

注意，我们不能使用已经投影的图，因为它不包含分量 ID。因此，我们将投影第二个包含先前计算出的分量 ID 的图。

以下代码将投影一个包含先前计算出的分量 ID 的新图

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

步骤 4

以下代码将使用 seedProperty 以 stream 模式运行算法

CALL gds.wcc.stream('myGraph-seeded', {
  seedProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
}) YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 20. 结果
名称 (name)	分量 ID (componentId)
"Alice"	0
“Charles”	0
“Bridget”	1
"Mats"	1
“Doug”	3
“Mark”	3
“Michael”	3

结果表明，尽管在投影时没有 seedProperty，节点 'Mats' 仍被分配到了与 'Bridget' 相同的分量中。这是正确的，因为这两个节点是连通的。

写入种子分量

在上一节中，我们演示了 seedProperty 在 stream 模式下的用法。它也适用于算法的其他模式。下面是一个如何在 write 模式下使用 seedProperty 的示例。请注意，下面的示例依赖于上一节中的步骤 1 - 3。

以下代码将使用 seedProperty 以 write 模式运行算法

CALL gds.wcc.write('myGraph-seeded', {
  seedProperty: 'componentId',
  writeProperty: 'componentId',
  relationshipWeightProperty: 'weight',
  threshold: 1.0
})
YIELD nodePropertiesWritten, componentCount;

表 21. 结果
nodePropertiesWritten	分量总数 (componentCount)
1	3

如果 seedProperty 配置参数与 writeProperty 具有相同的值，则算法仅为分量 ID 发生更改的节点写入属性。如果它们不同，则算法为所有节点写入属性。

图采样优化 (Graph Sampling optimization)

WCC 实现提供了两种计算策略

如 Wait-free Parallel Algorithms for the Union-Find Problem 中所述的非采样策略。
如 Optimizing Parallel Graph Connectivity Computation via Subgraph Sampling 中所述的采样策略。

虽然两种策略都提供了非常好的性能，但采样策略通常更快。决定使用哪种策略取决于输入图。如果图的关系是……

……无向的，算法选择采样策略。
……有向的，算法选择非采样策略。
……有向且反向索引的，算法选择采样策略。

关系的方向由可以在图投影期间设置的 orientation 定义。虽然 NATURAL 和 REVERSE 方向会导致有向图，但 UNDIRECTED 方向会导致无向关系。为了创建具有反向索引关系的定向图，可以在关系投影中使用 indexInverse 参数。反向索引允许算法根据相反的方向遍历节点的各种关系。如果图是使用 NATURAL 方向投影的，则反向索引代表 REVERSE 方向，反之亦然。

以下语句将使用带有反向索引的 Cypher 投影来投影上述示例图，并将其存储在图目录中，名称为 myIndexedGraph。

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myIndexedGraph',
  source,
  target,
  {},
  { inverseIndexedRelationshipTypes: ['*'] }
)

以下查询与上一节中的流示例相同。这一次，我们在 myIndexedGraph 上执行 WCC，这将允许算法使用采样策略。

以下代码将使用采样策略运行算法并流式输出结果

CALL gds.wcc.stream('myIndexedGraph')
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS name, componentId
ORDER BY componentId, name

表 22. 结果
名称 (name)	分量 ID (componentId)
"Alice"	0
“Bridget”	0
“Charles”	0
“Doug”	3
“Mark”	3
“Michael”	3

由于图采样优化中的随机性，实际分量 ID 可能会有所不同。在这种情况下，得到相反的解同样是可能的，例如，当我们的社区 0 节点被映射到社区 3，反之亦然。