K1 Coloring
This section describes the K1 Coloring algorithm in the Neo4j Graph Data Science library.
This algorithm is in the beta tier. For more information on algorithm tiers, see Algorithms.
1. Introduction
The K1 Coloring algorithm assigns a color to every node in the graph, trying to optimize for two objectives:

To make sure that every neighbor of a given node has a different color than the node itself.

To use as few colors as possible.
Note that the graph coloring problem is proven to be NPcomplete, which makes it intractable on anything but trivial graph sizes. For that reason the implemented algorithm is a greedy algorithm. Thus it is neither guaranteed that the result is an optimal solution, using as few colors as theoretically possible, nor does it always produce a correct result where no two neighboring nodes have different colors. However the precision of the latter can be controlled by the number of iterations this algorithm runs.
For more information on this algorithm, see:
Running this algorithm requires sufficient memory availability. Before running this algorithm, we recommend that you read Memory Estimation. 
2. Syntax
CALL gds.beta.k1coloring.stream(graphName: String, {
// additional configuration
})
YIELD nodeId, color
Name  Type  Default  Optional  Description 

graphName 
String 

yes 
The name of an existing graph on which to run the algorithm. If no graph name is provided, the configuration map must contain configuration for creating a graph. 
configuration 
Map 

yes 
Additional configuration, see below. 
Name  Type  Default  Optional  Description 

nodeProjection 
String 
null 
yes 
The projection of nodes to use when creating the implicit graph. 
relationshipProjection 
String 
null 
yes 
The projection of relationships to use when creating the implicit graph. 
concurrency 
Integer 
4 
yes 
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see :/installation/index.adoc#systemrequirementscpu. 
readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
Integer 
10 
yes 
The maximum number of iterations of K1 Coloring to run. 
Name  Type  Description 

nodeId 
Integer 
The ID of the Node 
color 
Integer 
The color of the Node 
CALL gds.beta.k1coloring.stats(
graphName: String,
configuration: Map
)
YIELD
nodes,
colorCount,
ranIterations,
didConverge,
configuration,
createMillis,
computeMillis
Name  Type  Default  Optional  Description 

graphNameOrConfig 
String or Map 

no 
Either the name of a graph stored in the catalog or a Map configuring the graph creation and algorithm execution. 
configuration 
Map 

yes 
Configuration for algorithmspecifics and/or graph filtering. Must be empty if graphNameOrConfig is a Map. 
Name  Type  Default  Optional  Description 

nodeProjection 
String 
null 
yes 
The projection of nodes to use when creating the implicit graph. 
relationshipProjection 
String 
null 
yes 
The projection of relationships to use when creating the implicit graph. 
concurrency 
Integer 
4 
yes 
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see :/installation/index.adoc#systemrequirementscpu. 
readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
Integer 
10 
yes 
The maximum number of iterations of K1 Coloring to run. 
Name  Type  Description 

nodeCount 
Integer 
The number of nodes considered. 
ranIterations 
Integer 
The actual number of iterations the algorithm ran. 
didConverge 
Boolean 
An indicator of whether the algorithm found a correct coloring. 
colorCount 
Integer 
The number of colors used. 
createMillis 
Integer 
Milliseconds for loading data. 
computeMillis 
Integer 
Milliseconds for running the algorithm. 
configuration 
Map 
The configuration used for running the algorithm. 
CALL gds.beta.k1coloring.mutate(graphName: String, configuration: Map)
YIELD nodes, colorCount, ranIterations, didConverge, configuration, createMillis, computeMillis, mutateMillis
The configuration for the mutate
mode is similar to the write
mode.
Instead of specifying a writeProperty
, we need to specify a mutateProperty
.
Also, specifying writeConcurrency
is not possible in mutate
mode.
myGraph
:CALL gds.beta.k1coloring.mutate('myGraph', { mutateProperty: 'color' })
CALL gds.beta.k1coloring.write(graphName: String, configuration: Map)
YIELD nodes, colorCount, ranIterations, didConverge, configuration, createMillis, computeMillis, writeMillis
Name  Type  Default  Optional  Description 

graphNameOrConfig 
String or Map 

no 
Either the name of a graph stored in the catalog or a Map configuring the graph creation and algorithm execution. 
configuration 
Map 

yes 
Configuration for algorithmspecifics and/or graph filtering. Must be empty if graphNameOrConfig is a Map. 
Name  Type  Default  Optional  Description 

nodeProjection 
String 
null 
yes 
The projection of nodes to use when creating the implicit graph. 
relationshipProjection 
String 
null 
yes 
The projection of relationships to use when creating the implicit graph. 
Integer 
4 
yes 
The number of concurrent threads used for running the algorithm. Also provides the default value for 'readConcurrency' and 'writeConcurrency'. This is dependent on the Neo4j edition; for more information, see :/installation/index.adoc#systemrequirementscpu. 

readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for writing the result. 

Integer 
10 
yes 
The maximum number of iterations of K1 Coloring to run. 

String 
n/a 
no 
The node property this procedure writes the color to. 
Name  Type  Description 

nodeCount 
Integer 
The number of nodes considered. 
ranIterations 
Integer 
The actual number of iterations the algorithm ran. 
didConverge 
Boolean 
An indicator of whether the algorithm found a correct coloring. 
colorCount 
Integer 
The number of colors used. 
write 
Boolean 
Specifies if the result was written back as a node property. 
createMillis 
Integer 
Milliseconds for loading data. 
computeMillis 
Integer 
Milliseconds for running the algorithm. 
writeMillis 
Integer 
Milliseconds for writing result data back to Neo4j. 
configuration 
Map 
The configuration used for running the algorithm. 
3. Examples
Consider the graph created by the following Cypher statement:
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)
This graph has a super node with name "Alice" that connects to all other nodes. It should therefore not be possible for any other node to be assigned the same color as the Alice node.
CALL gds.graph.create(
'myGraph',
'User',
{
LINK : {
orientation: 'UNDIRECTED'
}
}
)
We can now go ahead and create an inmemory graph with all the User
nodes and the LINK
relationships with UNDIRECTED
orientation.
In the examples below we will use named graphs and standard projections as the norm. However, Cypher projection and anonymous graphs could also be used. 
CALL gds.graph.create('myGraph', 'Person', 'LIKES')
In the following examples we will demonstrate using the K1 Coloring algorithm on this graph.
CALL gds.beta.k1coloring.stream('myGraph')
YIELD nodeId, color
RETURN gds.util.asNode(nodeId).name AS name, color
ORDER BY name
name  color 









It is also possible to write the assigned colors back to the database using the write
mode.
CALL gds.beta.k1coloring.write('myGraph', {writeProperty: 'color'})
YIELD nodeCount, colorCount, ranIterations, didConverge
nodeCount  colorCount  ranIterations  didConverge 





When using write
mode the procedure will return information about the algorithm execution.
In this example we return the number of processed nodes, the number of colors used to color the graph, the number of iterations and information whether the algorithm converged.
To instead mutate the inmemory graph with the assigned colors, the mutate
mode can be used as follows.
CALL gds.beta.k1coloring.mutate('myGraph', {mutateProperty: 'color'})
YIELD nodeCount, colorCount, ranIterations, didConverge
nodeCount  colorCount  ranIterations  didConverge 





Similar to the write
mode, stats
mode can run the algorithm and return only the execution statistics without persisting the results.
CALL gds.beta.k1coloring.stats('myGraph')
YIELD nodeCount, colorCount, ranIterations, didConverge
nodeCount  colorCount  ranIterations  didConverge 





Was this page helpful?