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 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，将不会记录进度百分比。
maxIterations	整数	`10`	是	K1 着色算法的最大运行迭代次数。
minCommunitySize	整数	`0`	是	仅返回社区大小大于或等于给定值的节点。
1. 在 GDS 会话中，默认值为可用处理器数量

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

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

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

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

表 5. 配置
名称	类型	默认值	可选	描述
concurrency	整数	4 ^[2]	是	用于运行算法的并发线程数。
jobId	字符串	内部生成	是	一个可提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	true	是	如果禁用，将不会记录进度百分比。
maxIterations	整数	10	是	K1 着色算法的最大运行迭代次数。
2. 在 GDS 会话中，默认值为可用处理器数量

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

表 10. 配置
名称	类型	默认值	可选	描述
concurrency	整数	4 ^[3]	是	用于运行算法的并发线程数。
jobId	字符串	内部生成	是	一个可提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	true	是	如果禁用，将不会记录进度百分比。
nodeLabels	字符串列表	['*']	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	['*']	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	4 ^[3]	是	用于运行算法的并发线程数。
jobId	字符串	内部生成	是	一个可提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	true	是	如果禁用，将不会记录进度百分比。
writeConcurrency	整数	'concurrency' 的值	是	用于将结果写入 Neo4j 的并发线程数。
maxIterations	整数	10	是	K1 着色算法的最大运行迭代次数。
minCommunitySize	整数	0	是	只有社区大小大于或等于给定值的社区 ID 才会被写入 Neo4j。
3. 在 GDS 会话中，默认值为可用处理器数量

表 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. 结果
名称	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`