最小权重 k-生成树

此功能处于 Alpha 阶段。有关功能层级的更多信息，请参阅 API 层级。

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

有时，我们可能需要一个生成树（节点之间通过单一路径连接的树），它不一定跨越图中的所有节点。K-生成树启发式算法返回一个包含 k 个节点和 k − 1 条关系的树。我们的启发式算法处理 Prim 算法在最小权重生成树问题中找到的结果。与 Prim 算法类似，它从给定的源节点开始，找到所有节点的生成树，然后使用启发式方法删除节点以生成一个包含 'k' 个节点的树。请注意，源节点不一定包含在最终输出中，因为启发式算法旨在找到一个全局最优的树。

考量

最小权重 k-生成树是 NP-Hard 问题。因此，Neo4j GDS 库中的算法不保证能找到最优解，但实际应用中应能提供良好的近似解。

类似于 Prim 算法，该算法仅关注源节点的连通分量。如果该分量包含的节点少于 k 个，它将不会查看其他分量，而是直接返回该分量。

语法

本节介绍在每种执行模式下运行 k-生成树启发式算法所使用的语法。我们将描述命名图变体的语法。要了解有关通用语法变体的更多信息，请参阅语法概述。

每种模式下的 K-生成树语法

以下将运行 k-生成树算法并写回结果

CALL gds.kSpanningTree.write(
  graphName: String,
  configuration: Map
)
YIELD effectiveNodeCount: Integer,
      preProcessingMillis: Integer,
      computeMillis: Integer,
      postProcessingMillis: Integer,
      writeMillis: Integer,
      configuration: Map

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签筛选命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型筛选命名图。将包含具有任何给定类型的关系。
concurrency	整数	`1`	是	该算法是单线程的，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	生成树将被写入的 Neo4j 数据库中的节点属性。
k	数字	`不适用`	否	要返回的树的大小
sourceNode	整数	`null`	不适用	起始源节点 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重方式运行。
objective	字符串	`'minimum'`	是	如果指定，该参数决定是寻找最小还是最大权重的 k-生成树。默认情况下，该过程寻找最小权重的 k-生成树。允许的值为 'minimum' 和 'maximum'。

表 3. 结果
名称	类型	描述
effectiveNodeCount	整数	访问的节点数。
preProcessingMillis	整数	数据预处理所需的毫秒数。
computeMillis	整数	运行算法所需的毫秒数。
postProcessingMillis	整数	算法结果后处理所需的毫秒数。
writeMillis	整数	写回结果数据所需的毫秒数。
configuration	映射	运行算法所使用的配置。

最小权重 k-生成树算法示例

在本节中，我们将展示在具体图上运行 k-生成树启发式算法的示例。目的是说明结果是什么样子，并提供在实际环境中如何使用该算法的指南。我们将在一个由少数节点以特定模式连接而成的小型道路网络图上进行演示。示例图如下所示：

以下将创建图中所示的示例图

CREATE (a:Place {id: 'A'}),
       (b:Place {id: 'B'}),
       (c:Place {id: 'C'}),
       (d:Place {id: 'D'}),
       (e:Place {id: 'E'}),
       (f:Place {id: 'F'}),
       (g:Place {id: 'G'}),
       (d)-[:LINK {cost:4}]->(b),
       (d)-[:LINK {cost:6}]->(e),
       (b)-[:LINK {cost:1}]->(a),
       (b)-[:LINK {cost:3}]->(c),
       (a)-[:LINK {cost:2}]->(c),
       (c)-[:LINK {cost:5}]->(e),
       (f)-[:LINK {cost:1}]->(g);

以下将投影并存储一个命名图

MATCH (source:Place)
OPTIONAL MATCH (source)-[r:LINK]->(target:Place)
RETURN gds.graph.project(
  'graph',
  source,
  target,
  { relationshipProperties: r { .cost } },
  { undirectedRelationshipTypes: ['*'] }
)

K-生成树示例

最小 K-生成树示例

在我们的示例图中，我们有 7 个节点。通过设置 k=3，我们定义要找到一个覆盖 3 个节点并具有 2 条关系的 3-最小生成树。

以下将运行 k-最小生成树算法并写回结果

MATCH (n:Place{id: 'A'})
CALL gds.kSpanningTree.write('graph', {
  k: 3,
  sourceNode: n,
  relationshipWeightProperty: 'cost',
  writeProperty:'kmin'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis,computeMillis,writeMillis, effectiveNodeCount;

以下将找到属于我们 k-生成树结果的节点

MATCH (n)
WITH n.kmin AS p, count(n) AS c
WHERE c = 3
MATCH (n)
WHERE n.kmin = p
RETURN n.id As Place, p as Partition

表 4. 结果
地点	分区
"A"	0
"B"	0
"C"	0

节点 A、B 和 C 构成了图中发现的 3-最小生成树。

最大 K-生成树示例

以下将运行 k-最大生成树算法并写回结果

MATCH (n:Place{id: 'D'})
CALL gds.kSpanningTree.write('graph', {
  k: 3,
  sourceNode: n,
  relationshipWeightProperty: 'cost',
  writeProperty:'kmax',
  objective: 'maximum'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis,computeMillis,writeMillis, effectiveNodeCount;

找到属于我们 k-生成树结果的节点

MATCH (n)
WITH n.kmax AS p, count(n) AS c
WHERE c = 3
MATCH (n)
WHERE n.kmax = p
RETURN n.id As Place, p as Partition

表 5. 结果
地点	分区
"C"	4
"D"	4
"E"	4

节点 C、D 和 E 构成了图中发现的 3-最大生成树。