强连通分量

强连通分量 (SCC) 算法在有向图中查找连接节点的最大集合。如果集合中的每对节点之间都存在有向路径，则该集合被认为是强连通分量。它通常在图分析过程的早期使用，以帮助我们了解图的结构。

此功能处于 Alpha 级别。有关功能级别的更多信息，请参见API 级别.

有向

词汇表

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

历史和解释

SCC 是最早的图算法之一，第一个线性时间算法由 Tarjan 在 1972 年描述。将有向图分解成其强连通分量是深度优先搜索算法的经典应用。

用例 - 何时使用强连通分量算法

在分析强大的跨国公司时，SCC 可用于查找公司集合，其中每个成员直接和/或间接拥有所有其他成员的股份。虽然它具有减少交易成本和增加信任等优势，但这种结构会削弱市场竞争。在 "全球公司控制网络" 中了解更多信息。
SCC 可用于在测量多跳无线网络中的路由性能时计算不同网络配置的连通性。在 "多跳无线网络中存在单向链路时的路由性能" 中了解更多信息
强连通分量算法可以用作许多仅在强连通图上工作的图算法的第一步。在社交网络中，一群人通常是强连通的（例如，一个班级的学生或任何其他共同的地方）。这些群体中的许多人通常喜欢一些共同的页面，或玩共同的游戏。SCC 算法可用于查找此类群体，并向尚未喜欢这些页面或游戏的群体成员推荐他们喜欢的页面或游戏。

语法

每个模式的分解语法

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

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

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
consecutiveIds	布尔值	`假`	是	用于确定组件标识符是否被映射到连续 ID 空间的标志（需要额外的内存）。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
componentId	整数	组件 ID。

以下将以统计模式运行算法

CALL gds.scc.stats(
  graphName: string,
  configuration: map
)
YIELD
  componentCount: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  componentDistribution: Map,
  configuration: Map

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
consecutiveIds	布尔值	`假`	是	用于确定组件标识符是否被映射到连续 ID 空间的标志（需要额外的内存）。

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

以下将运行算法并修改内存中的图

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

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中写入组件的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
consecutiveIds	布尔值	`假`	是	用于确定组件标识符是否被映射到连续 ID 空间的标志（需要额外的内存）。

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

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

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

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

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中写入组件的节点属性。
consecutiveIds	布尔值	`假`	是	用于确定组件标识符是否被映射到连续 ID 空间的标志（需要额外的内存）。

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

强连通分量算法示例

以下将创建一个示例图

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

CREATE (nAlice)-[:FOLLOW]->(nBridget)
CREATE (nAlice)-[:FOLLOW]->(nCharles)
CREATE (nMark)-[:FOLLOW]->(nDoug)
CREATE (nMark)-[:FOLLOW]->(nMichael)
CREATE (nBridget)-[:FOLLOW]->(nMichael)
CREATE (nDoug)-[:FOLLOW]->(nMark)
CREATE (nMichael)-[:FOLLOW]->(nAlice)
CREATE (nAlice)-[:FOLLOW]->(nMichael)
CREATE (nBridget)-[:FOLLOW]->(nAlice)
CREATE (nMichael)-[:FOLLOW]->(nBridget);

以下将投影并存储命名图

MATCH (source:User)-[r:FOLLOW]->(target:User)
RETURN gds.graph.project(
  'graph',
  source,
  target
)

内存估算

首先，我们将使用 `estimate` 过程估计运行算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 `write` 模式。估计算法有助于了解在您的图上运行算法对内存的影响。当您稍后在其中一种执行模式下实际运行算法时，系统将执行估计。如果估计表明执行有很高的概率超过其内存限制，则将禁止执行。要详细了解此内容，请参阅自动估计和执行阻止。

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

以下将估计运行算法所需的内存

CALL gds.scc.write.estimate('graph', { writeProperty: 'componentId' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	10	33332	33332	"32 KiB"

流

在 `stream` 执行模式下，算法返回每个节点的组件。这使我们能够直接检查结果或在 Cypher 中对它们进行后处理，而不会产生任何副作用。

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

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

CALL gds.scc.stream('graph', {})
YIELD nodeId, componentId
RETURN gds.util.asNode(nodeId).name AS Name, componentId AS Component
ORDER BY Component, Name DESC

表 14. 结果
名称	Component
`"Michael"`	`0`
`"Bridget"`	`0`
`"Alice"`	`0`
`"Charles"`	`3`
`"Mark"`	`4`
`"Doug"`	`4`

我们的示例图中存在 3 个强连通分量。

第一个也是最大的分量包含成员 Alice、Bridget 和 Michael，而第二大分量包含 Doug 和 Mark。Charles 独自形成一个分量，因为从该节点到其他任何节点都没有传出关系。

统计

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

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

以下将运行算法并以统计和测量值的形式返回结果

CALL gds.scc.stats('graph')
YIELD componentCount

表 15. 结果
componentCount
3

修改

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

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

以下将运行算法并将结果存储在 `graph` 中

CALL gds.scc.mutate('graph', { mutateProperty: 'componentId'})
YIELD componentCount

表 16. 结果
componentCount
3

写入

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

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