K-1 着色

有向

无向

异构节点

异构关系

加权关系

词汇表

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

介绍

K-1 着色算法为图中的每个节点分配一个颜色，试图优化两个目标

确保给定节点的每个邻居都与该节点本身具有不同的颜色。
尽可能少地使用颜色。

请注意，图着色问题被证明是 NP 完全的，这使得它除了在微不足道的图大小上以外变得难以处理。因此，实现的算法是贪婪算法。因此，它既不能保证结果是最优解，使用尽可能少的颜色，也不总是产生正确的结果，其中没有两个相邻的节点具有不同的颜色。但是，后者的精度可以通过该算法运行的迭代次数来控制。

有关此算法的更多信息，请参阅

运行此算法需要足够的内存可用。在运行此算法之前，我们建议您阅读内存估算。

语法

K-1 着色每种模式的语法

以下是运行算法和流式处理结果的 API 描述

CALL gds.k1coloring.stream(graphName: String, configuration: Map)
YIELD nodeId, color

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`null`	是	要运行算法的现有图的名称。如果未提供图名称，则配置映射必须包含用于创建图的配置。
configuration	映射	`{}`	是	其他配置，见下文。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
maxIterations	整数	`10`	是	要运行的 K1 着色的最大迭代次数。
minCommunitySize	整数	`0`	是	仅返回大小大于或等于给定值的社区内的节点。

表 3. 结果
名称	类型	描述
nodeId	整数	节点的 ID
color	整数	节点的颜色

以下是运行算法并返回计算统计信息的 API 描述

CALL gds.k1coloring.stats(
    graphName: String,
    configuration: Map
)
YIELD
    nodeCount,
    colorCount,
    ranIterations,
    didConverge,
    configuration,
    preProcessingMillis,
    computeMillis

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

表 5. 配置
名称	类型	默认值	可选	描述
concurrency	整数	4	是	用于运行算法的并发线程数。还提供“readConcurrency”和“writeConcurrency”的默认值。这取决于 Neo4j 版本；有关更多信息，请参见 CPU。
maxIterations	整数	10	是	要运行的 K1 着色的最大迭代次数。

表 6. 结果
名称	类型	描述
nodeCount	整数	所考虑的节点数。
ranIterations	整数	算法实际运行的迭代次数。
didConverge	布尔值	算法是否找到正确着色的指示器。
colorCount	整数	使用的颜色数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
configuration	映射	用于运行算法的配置。

以下是运行算法并修改投影图的 API 描述

CALL gds.k1coloring.mutate(graphName: String, configuration: Map)
YIELD nodeCount, colorCount, ranIterations, didConverge, configuration, preProcessingMillis, computeMillis, mutateMillis

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

“mutate”模式的配置类似于“write”模式。我们不需要指定“writeProperty”，而是需要指定“mutateProperty”。此外，在“mutate”模式下无法指定“writeConcurrency”。

表 8. 结果
名称	类型	描述
nodeCount	整数	所考虑的节点数。
ranIterations	整数	算法实际运行的迭代次数。
didConverge	布尔值	算法是否找到正确着色的指示器。
colorCount	整数	使用的颜色数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	将属性添加到投影图的毫秒数。
configuration	映射	用于运行算法的配置。

以下是运行算法并将结果写回 Neo4j 的 API 描述

CALL gds.k1coloring.write(graphName: String, configuration: Map)
YIELD nodeCount, colorCount, ranIterations, didConverge, configuration, preProcessingMillis, computeMillis, writeMillis

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

表 10. 配置
名称	类型	默认值	可选	描述
concurrency	整数	4	是	用于运行算法的并发线程数。还提供“readConcurrency”和“writeConcurrency”的默认值。这取决于 Neo4j 版本；有关更多信息，请参见 CPU。
writeConcurrency	整数	“concurrency”的值	是	用于写入结果的并发线程数。
maxIterations	整数	10	是	要运行的 K1 着色的最大迭代次数。
writeProperty	字符串	n/a	否	此过程将颜色写入的节点属性。
minCommunitySize	整数	0	是	仅将大小大于或等于给定值的社区的社区 ID 写入 Neo4j。

表 11. 结果
名称	类型	描述
nodeCount	整数	所考虑的节点数。
ranIterations	整数	算法实际运行的迭代次数。
didConverge	布尔值	算法是否找到正确着色的指示器。
colorCount	整数	使用的颜色数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回 Neo4j 的毫秒数。
configuration	映射	用于运行算法的配置。

示例

以下所有示例都应该在空数据库中运行。

这些示例使用 Cypher 投影作为规范。原生投影将在将来的版本中弃用。

考虑以下 Cypher 语句创建的图

CREATE (alice:User {name: 'Alice'}),
       (bridget:User {name: 'Bridget'}),
       (charles:User {name: 'Charles'}),
       (doug:User {name: 'Doug'}),

       (alice)-[:LINK]->(bridget),
       (alice)-[:LINK]->(charles),
       (alice)-[:LINK]->(doug),
       (bridget)-[:LINK]->(charles)

此图有一个名为“Alice”的超级节点，它连接到所有其他节点。因此，其他任何节点都不可能被分配与 Alice 节点相同的颜色。

MATCH (source:User)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

我们现在可以继续并使用所有 User 节点和具有 UNDIRECTED 方向的 LINK 关系来投影一个图。

以下语句将投影图并将其存储在图目录中。

MATCH (source:Person)-[r:LIKES]->(target:Person)
RETURN gds.graph.project(
  'myGraph',
  source,
  target
)

在以下示例中，我们将演示如何在这个图上使用 K-1 着色算法。

以流模式运行 K-1 着色算法

CALL gds.k1coloring.stream('myGraph')
YIELD nodeId, color
RETURN gds.util.asNode(nodeId).name AS name, color
ORDER BY name

表 12. 结果
name	color
`"Alice"`	`0`
`"Bridget"`	`1`
`"Charles"`	`2`
`"Doug"`	`1`

还可以使用 write 模式将分配的颜色写回数据库。

以写入模式运行 K-1 着色算法

CALL gds.k1coloring.write('myGraph', {writeProperty: 'color'})
YIELD nodeCount, colorCount, ranIterations, didConverge

表 13. 结果
nodeCount	colorCount	ranIterations	didConverge
`4`	`3`	`1`	`true`

使用 write 模式时，该过程将返回有关算法执行的信息。在此示例中，我们返回处理的节点数、用于对图进行着色的颜色数、迭代次数以及算法是否收敛的信息。

相反，可以使用 mutate 模式以如下方式修改内存中的图，使其包含分配的颜色。

以修改模式运行 K-1 着色算法

CALL gds.k1coloring.mutate('myGraph', {mutateProperty: 'color'})
YIELD nodeCount, colorCount, ranIterations, didConverge

表 14. 结果
nodeCount	colorCount	ranIterations	didConverge
`4`	`3`	`1`	`true`

与 write 模式类似，stats 模式可以运行算法并仅返回执行统计信息，而不会持久化结果。

以统计模式运行 K-1 着色算法

CALL gds.k1coloring.stats('myGraph')
YIELD nodeCount, colorCount, ranIterations, didConverge

表 15. 结果
nodeCount	colorCount	ranIterations	didConverge
`4`	`3`	`1`	`true`