K-1 着色

术语表

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

简介

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

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

请注意，图着色问题已被证明是 NP 完全问题，因此对于规模非平凡的图来说，它是难以计算的。出于这个原因，所实现的算法是一种贪心算法。因此，它既不能保证得到使用理论上最少颜色的最优解，也不能保证总是产生一个所有邻居节点颜色都不同的正确结果。不过，后者的精确度可以通过该算法运行的迭代次数来控制。

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

运行此算法需要足够的可用内存。在运行之前，建议您阅读内存估计 (Memory Estimation)。

语法

各模式下的 K-1 着色语法

以下描述了用于运行算法并流式传输结果的 API

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

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

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

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

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

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

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

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

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

以下描述了用于运行算法并修改内存中投影图的 API

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

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

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	不适用	否	GDS 图中用于写入颜色的节点属性。
nodeLabels	字符串列表	['*']	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	['*']	是	使用给定的关系类型过滤命名图。
concurrency	整数	4	是	用于运行算法的并发线程数。
logProgress	布尔值	true	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	内部生成	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
maxIterations	整数	10	是	K-1 着色运行的最大迭代次数。

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

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

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

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

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

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

示例

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

这些示例将 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

表 13. 结果
名称 (name)	颜色
`"Alice"`	`0`
`“Bridget”`	`1`
`“Charles”`	`2`
`“Doug”`	`1`

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

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

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

表 14. 结果
nodeCount	颜色计数	ranIterations	didConverge
`4`	`3`	`1`	`true`

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

如果希望使用分配的颜色修改内存中的图，可以使用如下的 mutate 模式。

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

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

表 15. 结果
nodeCount	颜色计数	ranIterations	didConverge
`4`	`3`	`1`	`true`

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

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

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

表 16. 结果
nodeCount	颜色计数	ranIterations	didConverge
`4`	`3`	`1`	`true`