Leiden algorithm

The Leiden algorithm is an improvement over the Louvain algorithm that guarantees well-connected communities. It adds a refinement phase before each aggregation step. This avoids Louvain's known shortcoming of producing arbitrarily badly connected or disconnected clusters. Like Louvain, it optimizes modularity through hierarchical clustering and can run in both weighted and unweighted modes. Leiden is particularly suited for applications where community cohesion matters. Use cases include detecting tightly-knit fraud rings in financial networks, identifying functionally coherent modules in biological systems, and discovering well-connected user groups in social platforms.

The key improvement in Leiden is a refinement phase that occurs before each aggregation step. After the algorithm identifies candidate communities, the refinement phase processes each community from the bottom up. It merges nodes in a way that guarantees the resulting communities remain connected. This addresses a known shortcoming of Louvain, which can produce arbitrarily badly connected or even disconnected communities.

The algorithm can run in unweighted or weighted mode based on the graph and user inputs. When an edge weight property is specified, the algorithm runs in weighted mode.

Here are several real-world applications of the Leiden algorithm for community detection:

The Leiden algorithm is particularly useful in these cases because it:

.leiden syntax

CALL neptune.algo.leiden(
  [node list (required)],
  {
    vertexLabels: [list of vertex labels for filtering (optional)],
    edgeLabels: [list of edge labels for filtering (optional)],
    edgeWeightProperty: a numeric edge property to use as weight (optional),
    edgeWeightType: numeric type of the specified edgeWeightProperty (optional),
    maxLevels: maximum number of levels to optimize at (optional, default: 10),
    maxIterations: maximum number of iterations per level (optional, default: 10),
    levelTolerance: minimum modularity change to continue to next level (optional, default: 0.01),
    iterationTolerance: minimum modularity change to continue to next iteration (optional, default: 0.0001),
    theta: temperature parameter for refinement phase (optional, default: 0.05),
    concurrency: number of threads to use (optional)
  }
)
YIELD node, community
RETURN node, community

.leiden inputs

.leiden outputs

For each source node:

If the input node list is empty, the output is also empty.

.leiden query examples

The following example runs the Leiden algorithm in unweighted mode:

CALL neptune.algo.leiden(
  ["101"],
  {
    vertexLabels: ["airport"],
    edgeLabels: ["route"],
    maxLevels: 3,
    maxIterations: 10,
    theta: 0.05
  }
)
YIELD node, community
RETURN node, community

The following example runs the Leiden algorithm in weighted mode using edge weights:

Sample use case: you may want to identify natural communities of stops where there is high intra-connectivity — essentially, clusters of stops that are strongly interconnected based on passenger traffic

CALL neptune.algo.leiden(
  ["101"],
  {
    vertexLabels: ["airport"],
    edgeLabels: ["route"],
    maxLevels: 3,
    maxIterations: 10,
    edgeWeightProperty: "weight",
    edgeWeightType: "int",
    theta: 0.5
  }
)
YIELD node, community
RETURN node, community

This is a query integration example, where .leiden uses the output of a preceding MATCH clause as its node list:

MATCH (n)
CALL neptune.algo.leiden(
  n,
  {
    vertexLabels: ["airport"],
    edgeLabels: ["route"],
    maxLevels: 1,
    maxIterations: 10,
    edgeWeightProperty: "weight",
    edgeWeightType: "int",
    theta: 0.01
  }
)
YIELD community
RETURN n, community

Sample .leiden output

Here is an example of the output returned by .leiden when run against the sample air-routes dataset [nodes], and sample air-routes dataset [edges], when using the following query:

aws neptune-graph execute-query \
    --graph-identifier ${graphIdentifier} \
    --query-string 'MATCH (n) \
            CALL neptune.algo.leiden(n) \
            YIELD node, community \
            RETURN node, community \
            LIMIT 2' \
    --language open_cypher \
    /tmp/out.txt
cat /tmp/out.txt
{
"results": [{
 "node": {
   "~id": "10",
   "~entityType": "node",
   "~labels": ["airport"],
   "~properties": {
     "lat": 38.944499970000003,
     "elev": 313,
     "type": "airport",
     "code": "IAD",
     "lon": -77.455802919999996,
     "runways": 4,
     "longest": 11500,
     "city": "Washington D.C.",
     "region": "US-VA",
     "desc": "Washington Dulles International Airport",
     "degree": 312,
     "country": "US",
     "icao": "KIAD"
   }
 },
 "community": 1
 }, {
 "node": {
   "~id": "12",
   "~entityType": "node",
   "~labels": ["airport"],
   "~properties": {
     "lat": 40.639801030000001,
     "elev": 12,
     "type": "airport",
     "code": "JFK",
     "lon": -73.778900149999998,
     "runways": 4,
     "longest": 14511,
     "city": "New York",
     "region": "US-NY",
     "desc": "New York John F. Kennedy International Airport",
     "degree": 403,
     "country": "US",
     "icao": "KJFK"
   }
 },
 "community": 1
 }]
}