最小权重 k-生成树

术语表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不能在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法有能力区分不同类型的节点。
异构节点: 异构节点允许。该算法平等对待所有选定的节点，无论其标签如何。
异构关系: 异构关系完全支持。该算法有能力区分不同类型的关系。
异构关系: 异构关系允许。该算法平等对待所有选定的关系，无论其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 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	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

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

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

最小权重 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-最大生成树。