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 Chapter 5, Algorithms.
This topic includes:
The K1 Coloring algorithm assigns a color to every node in the graph, trying to optimize for two objectives:
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 Section 3.1, “Memory Estimation”. 
The following describes the API for running the algorithm and stream results:
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 Section 2.5.2, “CPU”. 
readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
maxIterations 
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 
The following describes the API for running the algorithm and returning the computation statistics:
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 Section 2.5.2, “CPU”. 
readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
maxIterations 
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. 
The following describes the API for running the algorithm and mutating the inmemory graph:
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.
The following will run the algorithm and store the results in myGraph
:
CALL gds.beta.k1coloring.mutate('myGraph', { mutateProperty: 'color' })
The following describes the API for running the algorithm and writing results back to Neo4j:
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. 
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 Section 2.5.2, “CPU”. 
readConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for reading the graph. 
writeConcurrency 
Integer 
value of 'concurrency' 
yes 
The number of concurrent threads used for writing the result. 
maxIterations 
Integer 
10 
yes 
The maximum number of iterations of K1 Coloring to run. 
writeProperty 
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. 
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. 
The following statement will create the graph and store it in the graph catalog.
CALL gds.graph.create('myGraph', 'Person', 'LIKES')
In the following examples we will demonstrate using the K1 Coloring algorithm on this graph.
Running the K1 Coloring algorithm in stream mode:
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.
Running the K1 Coloring algorithm in 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.
Running the K1 Coloring algorithm in mutate mode:
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.
Running the K1 Coloring algorithm in stats mode:
CALL gds.beta.k1coloring.stats('myGraph')
YIELD nodeCount, colorCount, ranIterations, didConverge
nodeCount  colorCount  ranIterations  didConverge 




