Leiden Algorithm

Introduction

The Leiden algorithm is a hierarchical community detection method. It groups nodes into communities that are densely connected internally while remaining sparsely connected to the rest of the graph, and it repeats that grouping over several levels, so communities found at one level are themselves grouped at the next.

Leiden extends the Louvain method with a refinement phase. Before a level is collapsed into the next one, each community is broken back down into well-connected sub-groups, and only those sub-groups are merged together. A community is therefore never carried forward as a block whose internal structure does not justify it, which is what allows Leiden to guarantee that every community it reports is internally connected. On the same graph, Leiden usually reaches a slightly higher quality score than Louvain, at the cost of extra work per level. Louvain remains a reasonable choice when runtime matters more than the last increment of quality.

Quality functions

The objective parameter selects the quality function that the algorithm optimizes, and gamma sets its resolution.

modularity (the default) measures how much denser the connections inside a community are than they would be in a random graph with the same degree distribution. Raising gamma above 1.0 favors more and smaller communities, and lowering it favors fewer and larger ones.
cpm is the Constant Potts Model, which compares the internal density of a community against the fixed target density gamma. Because that target does not depend on the size of the graph, CPM avoids the resolution limit of modularity, where small communities in a large graph tend to be absorbed into larger ones. Useful values of gamma under CPM are typically well below 1.0, and they depend on how dense the graph is.

Execution

Each level of the hierarchy runs either as distributed SQL or in memory on a single node. A level runs in memory once its graph has no more nodes than largeCommunityThreshold, which for a typical run means the first level or two are distributed and the smaller aggregated levels that follow are not. Set largeCommunityThreshold to 0 to force every level through the distributed path.

Set seed to make a run reproducible. Note that distributed levels sum floating point weights in a nondeterministic order, so two runs with the same seed can still differ when the choice between two candidate communities comes down to a near exact tie.

Output

The algorithm produces the following fields:

Field Name	Description
id	The ID of the node (vertex)
communityId	A generated integer ID representing the community of the node (vertex)
intermediateCommunityIds	Community identifiers for the node at each hierarchy level

Query Example

cyphergremlin

CALL algo.leiden({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    maxIterations: 30,
    relationshipWeightProperty: 'weight',
    maxLevels: 10,
    threshold: 0.0001,
    largeCommunityThreshold: 100000,
    seed: 42
    }) YIELD id, communityId
RETURN id, communityId

graph.program(
  LeidenProgram.build()
    .vertices("User")
    .edges("LINK")
    .maxIteration(30)
    .maxLevels(10)
    .setParams("weight", "weight", "threshold", 0.0001, "largeCommunityThreshold", 100000, "seed", 42)
    .create()
).submitAndGet().toList()

Using the CPM quality function

cyphergremlin

CALL algo.leiden({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    objective: 'cpm',
    gamma: 0.05
    }) YIELD id, communityId, intermediateCommunityIds
RETURN id, communityId, intermediateCommunityIds

graph.program(
  LeidenProgram.build()
    .vertices("User")
    .edges("LINK")
    .setParams("objective", "cpm", "gamma", 0.05)
    .create()
).submitAndGet().toList()

Parameters

cyphergremlin

Name	Description	Required	Default Value
labels	Specifies the node labels to include in the algorithm	Yes
relationshipTypes	Specifies the relationship types to include	Yes
maxIterations	Maximum number of iterations within a hierarchy level	No	30
relationshipWeightProperty	Defines the property name for edge weights	No
maxLevels	Maximum hierarchy depth for community detection	No	10
threshold	Minimum quality change required between iterations	No	0.0001
objective	Quality function to optimize, either `modularity` or `cpm`	No	modularity
gamma	Resolution of the quality function	No	1.0
largeCommunityThreshold	Node count at or below which a hierarchy level is processed in memory	No	100000
seed	Random number generator seed for reproducible results	No

Method	Description	Required	Default Value
vertices(String... names)	Specifies the node (vertex) labels to include	Yes
edges(String... names)	Specifies the edge labels to include	Yes
maxIteration(int n)	Sets the maximum iteration count within a hierarchy level	No	30
maxLevels(int n)	Maximum hierarchy depth for community detection	No	10
setParams(Object... args)	Adds additional parameters using alternating keys and values	No	see below

Additional parameter keys in setParams

Key	Description	Default Value
weight	Specifies the edge weight property or a constant value as weight	1.0
threshold	Minimum quality change required between iterations	0.0001
objective	Quality function to optimize, either `modularity` or `cpm`	modularity
gamma	Resolution of the quality function	1.0
largeCommunityThreshold	Node count at or below which a hierarchy level is processed in memory	100000
seed	Random number generator seed for reproducible results

Exporting Query Results

For large datasets, export the results to object storage. An administrator registers the export locations, and a query names one of them plus the directory to write under, as <location>:<directory>. See Exporting Query Results for registering a location and for the supported storage types and file formats.

cyphergremlin

EXPORT TO 'my_export_location:leiden_results'
CALL algo.leiden({
    labels: ['User'],
    relationshipTypes: ['LINK'],
    relationshipWeightProperty: 'weight',
    maxLevels: 10
    }) YIELD id, communityId
RETURN id, communityId

graph.program(
    LeidenProgram.build()
            .maxIteration(20)
            .vertices("User")
            .edges("LINK")
            .setParams("weight", "amount", "threshold", 0.001)
            .create()
).submitAndSave([
  "exportTo": "my_export_location:leiden_results"
])