强连通分量

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

有向

无向

异构节点

异构关系

加权关系

术语表

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

历史与解释

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

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

在分析强大的跨国公司时，SCC 可用于查找这样一组公司，其中每个成员直接和/或间接拥有其他所有成员的股份。尽管这种结构具有降低交易成本和增加信任等优点，但它可能削弱市场竞争。“全球企业控制网络”中提供了更多信息。
在测量多跳无线网络中的路由性能时，SCC 可用于计算不同网络配置的连通性。在“存在单向链路的多跳无线网络中的路由性能”中阅读更多内容。
强连通分量算法可以作为许多仅适用于强连通图的图算法的第一步。在社交网络中，一群人通常是强连通的（例如，一个班级的学生或任何其他共同场所）。这些群体中的许多人通常喜欢一些共同的页面或玩共同的游戏。SCC 算法可以用来找到这样的群体，并向群体中尚未喜欢这些页面或游戏的人推荐这些共同喜欢的页面或游戏。

语法

每种模式的分解语法

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

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

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

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

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

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

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

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

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

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

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

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	字符串	`不适用`	否	目录中存储的图的名称。
配置	映射	`{}`	是	用于算法特定设置和/或图过滤的配置。

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

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

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

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	字符串	`不适用`	否	目录中存储的图的名称。
配置	映射	`{}`	是	用于算法特定设置和/或图过滤的配置。

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

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

强连通分量算法示例

以下将创建一个示例图

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. 结果
节点数量	关系数量	最小字节数	最大字节数	所需内存
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. 结果
名称	分量
`"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. 结果
分量计数
3

修改模式

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

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

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

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

表 16. 结果
分量计数
3

写入模式

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

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