Leiden

Overview

The Leiden algorithm is a community detection algorithm designed to maximize modularity in a graph. It was developed to address potential issues in the results obtained by the popular Louvain algorithm, where some communities may not be well-connected or even disconnected. The Leiden algorithm is faster compared to the Louvain algorithm and guarantees to produce partitions in which all communities are internally connected. The algorithm is also named after the location of its authors.

• 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 is explained in the Louvain algorithm. The modularity formula used in the Leiden algorithm is extended to handle different levels of community granularity:

γ > 0 is the resolution parameter that modulates the density of connections within communities and between communities. When γ > 1, it leads to more, smaller and well-connected communities; when γ < 1, it leads to fewer, larger and less well-connected communities.

Leiden

The Leiden algorithm starts from a singleton partition, in which each node is in its own community. Then algorithm iteratively runs through passes, and each pass is made of three phases:

First Phase: Fast Modularity Optimization

Unlike the first phase of the Louvain algorithm, which keeps visiting all nodes in the graph until no node movements can increase the modularity; the Leiden algorithm takes a more efficient approach, it only visits all nodes once, afterwards it visits only nodes whose neighborhood has changed. To do that, the Leiden algorithm maintains a queue and initializes it by adding all nodes in the graph in a random order.

Then repeat the following steps until the queue is empty:

• Remove the first node from the front of the queue.
• Reassign the node to a different community which has the maximum gain of modularity (ΔQ); or keep the node in its original community if there is no positive gain.
• If the node is moved to a different community, add to the rear of the queue all neighbors of the node that do not belong to the node’s new community and that are not yet in the queue.

The first phase ends with a partition P of the base or aggregate graph.

Second Phase: Refinement

This phase is designed to get a refined partition P_refined of P to guarantee that all communities are well-connected.

P_refined is initially set to a singleton partition, in which each node in the base or aggregate graph is in its own community. Refine each community C ∈ P as follows.

1. Consider only nodes v ∈ C that are well-connected within C:

where,

• W(v,C-v) is the sum of edge weights between node v and the rest of nodes in C;
• k_v is the sum of weights of all edges attached to node v;
• $\sum _{\mathrm{tot}}^c$ the sum of weights of all edges attached to nodes in C.

Take community C₁ in the above graph as 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

In this case, only nodes a and d are considered well-connected in community C₁.

2. Visit each node v in random order, if it is still on its own in a community in P_refined, randomly merge it to a community C' ∈ P_refined for which the modularity increases. It is required that C' must be well-connected with C:

Note that in this phase, each node is not necessarily greedily merged with the community that yields the maximum gain of modularity. However, the larger the gain, the more likely a community is to be selected. The degree of randomness in the selection of a community is determined by a parameter θ > 0:

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

After the refinement phase is concluded, communities in P often are split into multiple communities in P_refined, but not always.

Third Phase: Community Aggregation

The aggregate graph is created based on P_refined. However, the partition for the aggregate graph is based on P. The aggregation process is the same as Louvain.

P - color blocks, P_refined - node colors

Once this third phase is completed, another pass is applied to the aggregate graph. The passes are iterated until there are no more changes, and a maximum modularity is attained.

Considerations

• If node i has any self-loop, when calculating k_i, the weight of self-loop is counted only once.
• The Leiden algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(leiden)
• Parameters:

Examples

File Writeback

UQL
algo(leiden).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}).write({
  file:{
    filename_community_id: 'communityID',
    filename_ids: 'ids',
    filename_num: 'num'
  }
})

Property Writeback

UQL
algo(leiden).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}).write({
  db:{
    property: 'communityID'
  }
})

Direct Return

UQL
algo(leiden).params({ 
  phase1_loop_num: 6, 
  min_modularity_increase: 0.5,
  edge_schema_property: 'weight'
}) as results, stats
return results, stats

Stream Return

UQL
algo(leiden).params({ 
  phase1_loop_num: 6, 
  min_modularity_increase: 0.5,
  edge_schema_property: 'weight'
}).stream() as results
group by results.community_id
return table(results.community_id, max(results._uuid))

UQL
algo(leiden).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  order: "desc"
}).stream({
  mode: 2
}) as results
return results

Stats Return

UQL
algo(leiden).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1
}).stats() as stats
return stats