最小权重 k-生成树

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

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

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

注意事项

最小权重 k-生成树是 NP 难问题。因此，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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定设置和/或图过滤的配置。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有任何给定类型的关系。
concurrency	整数	`1`	是	该算法是单线程的，更改并发参数对运行时没有影响。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中用于写入生成树的节点属性。
k	数字	`n/a`	否	要返回的树的大小
sourceNode	整数	`null`	n/a	起始源节点 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-最大生成树。