Leiden

Overview

The Leiden algorithm is a community detection method designed to optimize modularity while addressing some of the limitations of the widely used Louvain algorithm. Unlike Louvain, which may produce poorly connected or even disconnected communities, Leiden guarantees well-connected communities. Additionally, the Leiden algorithm is faster. It is named after the city of Leiden, where it was developed.

References:

• V.A. Traag, L. Waltman, N.J. van Eck, From Louvain to Leiden: guaranteeing well-connected communities (2019)
• V.A. Traag, P. Van Dooren, Y. Nesterov, Narrow scope for resolution-limit-free community detection (2011)

Concepts

Modularity

The concept of modularity, as explained in the Louvain algorithm, is also used in the Leiden algorithm. However, Leiden introduces a new resolution parameter γ (gamma) into the modularity formula:

The parameter γ controls the granularity of the detected communities by modulating the balance between intra-community and inter-community connections:

• When γ > 1, the algorithm favors more and smaller communities that are tightly connected internally.
• When 0 < γ < 1, it favors fewer and larger communities that may be less densely connected internally.

Leiden

When the Leiden algorithm starts, each node is placed in its own community. The algorithm then iteratively proceeds through passes, each consisting of three phases:

First Phase: Fast Modularity Optimization

In the first phase of Louvain, the algorithm repeatedly visits all nodes in the graph until no further node movements can increase the modularity. The Leiden algorithm improves efficiency by only visiting all nodes once initially, and afterwards, only revisiting nodes whose neighborhoods have changed.

To achieve this, the Leiden algorithm maintains a queue, initializes it with all nodes in the graph in a random order, then repeats the following steps until the queue is empty:

• Remove the first node v from the front of the queue.
• Reassign node v to a different community C that provides the maximum gain of modularity (ΔQ), or keep v in its current community if there is no positive gain.
• If v is moved to a new community C, add to the rear of the queue all neighbors of v that do not belong to C and that are not already in the queue.

Second Phase: Refinement

This phase produces a refined partition Prefined based on the partition P obtained from the first phase. Initially, Prefined is set as a singleton partition, where each node—either from the original graph or the aggregated graph—is placed in its own community. Then, each community C ∈ P is refined individually as follows:

1. Find each node v ∈ C that is well-connected within C by this formula:

where,

• W(v,C-v) is the sum of edge weights between node v and the other nodes in C.
• kv is the total edge weights between node v and the other nodes in the graph.
• $\sum _{\mathrm{tot}}^c$ is the sum of k of all nodes in C.
• m is the sum of all edge weights in the graph.

Take community C1 in the graph above as an example, where

• m = 18.1
• = k_a + k_b + k_c + k_d = 6 + 2.7 + 2.8 + 3 = 14.5

Set γ as 1.2, then:

• W(a, C₁) - γ/m ⋅ k_a ⋅ ( - k_a) = 4.5 - 1.2/18.1*6*(14.5 - 6) = 1.12
• W(b, C₁) - γ/m ⋅ k_b ⋅ ( - k_b) = 1 - 1.2/18.1*2.7*(14.5 - 2.7) = -1.11
• W(c, C₁) - γ/m ⋅ k_c ⋅ ( - k_c) = 0.5 - 1.2/18.1*2.8*(14.5 - 2.8) = -1.67
• W(d, C₁) - γ/m ⋅ k_d ⋅ ( - k_d) = 3 - 1.2/18.1*3*(14.5 - 3) = 0.71

Therefore, nodes a and d are considered well-connected in C1.

2. Visit each node v. If it remains in its own singleton community in Prefined, randomly merge it into a community C' ∈ Prefined that increases the modularity. The merge is allowed only if C' is well-connected with C, determined by the following condition:

Note that each node v is not necessarily merged greedily with the community that yields the maximum gain of modularity. Instead, the larger the modularity gain, the more likely that community is to be selected. The degree of randomness in selecting a community C' is determined by a parameter θ (theta) as:

Randomness in the selection of a community allows the partition space to be explored more broadly.

Third Phase: Community Aggregation

The aggregate graph is constructed based on the Prefined obtained from the previous phase. This aggregation process is the same as in Louvain. Note that each node is a single community in the aggregate graph in Louvain. However, the aggregate graph in Leiden is partitioned based on P, so multiple nodes may belong to the same community.

P is denoted by color blocks, Prefined is denoted by node colors

Once this third phase is completed, another pass is applied to the aggregate graph. These passes are iterated until no further changes occur in the node communities, and the modularity reaches its maximum.

Considerations

• If node v has any self-loop, when calculating kv, the weight of self-loop is counted only once.
• The Leiden algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
ALTER EDGE default ADD PROPERTY {
    weight float
};
INSERT (A:default {_id: "A"}),
       (B:default {_id: "B"}),
       (C:default {_id: "C"}),
       (D:default {_id: "D"}),
       (E:default {_id: "E"}),
       (F:default {_id: "F"}),
       (G:default {_id: "G"}),
       (H:default {_id: "H"}),
       (I:default {_id: "I"}),
       (J:default {_id: "J"}),
       (K:default {_id: "K"}),
       (L:default {_id: "L"}),
       (M:default {_id: "M"}),
       (N:default {_id: "N"}),
       (A)-[:default {weight: 1}]->(B),
       (A)-[:default {weight: 1.7}]->(C),
       (A)-[:default {weight: 0.6}]->(D),
       (A)-[:default {weight: 1}]->(E),
       (B)-[:default {weight: 3}]->(G),
       (F)-[:default {weight: 1.6}]->(A),
       (F)-[:default {weight: 0.3}]->(H),
       (F)-[:default {weight: 2}]->(J),
       (F)-[:default {weight: 0.5}]->(K),
       (G)-[:default {weight: 2}]->(F),
       (I)-[:default {weight: 1}]->(F),
       (K)-[:default {weight: 0.3}]->(A),
       (K)-[:default {weight: 0.8}]->(L),
       (K)-[:default {weight: 1.2}]->(M),
       (K)-[:default {weight: 2}]->(N);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: leiden

File Writeback

This algorithm can generate three files:

GQLUQL
CALL algo.leiden.write("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}, {
  file: {
    filename_community_id: "f1",
    filename_ids: "f2",
    filename_num: "f3"
  }
})

Result:

File: f2File: f3
community_id,_ids
5,I;J;F;H;
7,G;B;
9,D;A;E;C;
11,N;L;K;M;

DB Writeback

Writes the community_id values from the results to the specified node property. The property type is uint32.

GQLUQL
CALL algo.leiden.write("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}, {
  db: {
    property: "communityID"
  }
})

Stats Writeback

GQLUQL
CALL algo.leiden.write("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}, {
  stats: {}
})

Result:

Full Return

GQLUQL
CALL algo.leiden.run("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1
}) YIELD r
RETURN r

Result:

Stream Return

This Stream Return supports two modes:

GQLUQL
CALL algo.leiden.stream("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 6, 
  min_modularity_increase: 0.1
}) YIELD r
RETURN r

Result:

GQLUQL
CALL algo.leiden.stream("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 6, 
  min_modularity_increase: 0.1
}, {
  mode: 2
}) YIELD r
RETURN r

Result:

Stats Return

GQLUQL
CALL algo.leiden.stats("my_hdc_graph", {
  return_id_uuid: "id",
  phase1_loop_num: 6, 
  min_modularity_increase: 0.1
}) YIELD s
RETURN s

Result: