# Leiden algorithm

Part of a series on :
Network science :
Theory :
Graph
Complex network
Contagion
Small-world
Scale-free
Community structure
Percolation
Evolution
Controllability
Graph drawing
Social capital
Link analysis
Optimization
Reciprocity
Closure
Homophily
Transitivity
Preferential attachment
Balance theory
Network effect
Social influence :
Network types :
Informational (computing)
Telecommunication
Transport
Social
Scientific collaboration
Biological
Artificial neural
Interdependent
Semantic
Spatial
Dependency
Flow
on-Chip :
Graphs :
MetricsAlgorithms :
Centrality
Degree
Motif
Clustering
Degree distribution
Assortativity
Distance
Modularity
Efficiency :
Models :
ListsCategories :
Topics
Software
Network scientists
Category:Network theory
Category:Graph theory :
vte :
The Leiden algorithm is a community detection algorithm developed by Traag et al at Leiden University. It was developed as a modification of the Louvain method. Like the Louvain method, the Leiden algorithm attempts to optimize modularity in extracting communities from networks; however, it addresses key issues present in the Louvain method, namely poorly connected communities and the resolution limit of modularity.

## Improvement over Louvain method

Broadly, the Leiden algorithm uses the same two primary phases as the Louvain algorithm: a local node moving step (though, the method by which nodes are considered in Leiden is more efficient) and a graph aggregation step. However, to address the issues with poorly-connected communities and the merging of smaller communities into larger communities (the resolution limit of modularity), the Leiden algorithm employs an intermediate refinement phase in which communities may be split to guarantee that all communities are well-connected.
Consider, for example, the following graph:
Three communities are present in this graph (each color represents a community). Additionally, the center "bridge" node (represented with an extra circle) is a member of the community represented by blue nodes. Now consider the result of a node-moving step which merges the communities denoted by red and green nodes into a single community (as the two communities are highly connected):
Notably, the center "bridge" node is now a member of the larger red community after node moving occurs (due to the greedy nature of the local node moving algorithm). In the Louvain method, such a merging would be followed immediately by the graph aggregation phase. However, this causes a disconnection between two different sections of the community represented by blue nodes. In the Leiden algorithm, the graph is instead refined:
The Leiden algorithm's refinement step ensures that the center "bridge" node is kept in the blue community to ensure that it remains intact and connected, despite the potential improvement in modularity from adding the center "bridge" node to the red community.

## Graph components

Before defining the Leiden algorithm, it will be helpful to define some of the components of a graph.

### Vertices and edges

A graph is composed of vertices (nodes) and edges. Each edge is connected to two vertices, and each vertex may be connected to zero or more edges. Edges are typically represented by straight lines, while nodes are represented by circles or points. In set notation, let $V$ be the set of vertices, and $E$ be the set of edges:
${\begin{aligned}V&:=\{v_{1},v_{2},\dots ,v_{n}\}\\E&:=\{e_{ij},e_{ik},\dots ,e_{kl}\}\end{aligned}}$
where $e_{ij}$ is the directed edge from vertex $v_{i}$ to vertex $v_{j}$. We can also write this as an ordered pair:
${\begin{aligned}e_{ij}&:=(v_{i},v_{j})\end{aligned}}$

### Community

A community is a unique set of nodes:
${\begin{aligned}C_{i}&\subseteq V\\C_{i}&\bigcap C_{j}=\emptyset ~\forall ~i\neq j\end{aligned}}$
and the union of all communities must be the total set of vertices:
${\begin{aligned}V&=\bigcup _{i=1}C_{i}\end{aligned}}$

### Partition

A partition is the set of all communities:
${\begin{aligned}{\mathcal {P}}&=\{C_{1},C_{2},\dots ,C_{n}\}\end{aligned}}$

## Partition Quality

How communities are partitioned is an integral part on the Leiden algorithm. How partitions are decided can depend on how their quality is measured. Additionally, many of these metrics contain parameters of their own that can change the outcome of their communities.

### Modularity

Modularity is a highly used quality metric for assessing how well a set of communities partition a graph. The equation for this metric is defined for an adjacency matrix, A, as:
$Q={\frac {1}{2m}}\sum _{ij}(A_{ij}-{\frac {k_{i}k_{j}}{2m}})\delta (c_{i},c_{j})$
where:
* $A_{ij}$ represents the edge weight between nodes $i$ and $j$; see Adjacency matrix;
* $k_{i}$ and $k_{j}$ are the sum of the weights of the edges attached to nodes $i$ and $j$, respectively;
* $m$ is the sum of all of the edge weights in the graph;
* $c_{i}$ and $c_{j}$ are the communities to which the nodes $i$ and $j$ belong; and
* $\delta$ is Kronecker delta function:
${\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same community}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}$

### Reichardt Bornholdt Potts Model (RB)

One of the most well used metrics for the Leiden algorithm is the Reichardt Bornholdt Potts Model (RB). This model is used by default in most mainstream Leiden algorithm libraries under the name RBConfigurationVertexPartition. This model introduces a resolution parameter $\gamma$ and is highly similar to the equation for modularity. This model is defined by the following quality function for an adjacency matrix, A, as:
$Q=\sum _{ij}(A_{ij}-\gamma {\frac {k_{i}k_{j}}{2m}})\delta (c_{i},c_{j})$
where:
* $\gamma$ represents a linear resolution parameter

### Constant Potts Model (CPM)

Another metric similar to RB, is the Constant Potts Model (CPM). This metric also relies on a resolution parameter $\gamma$ The quality function is defined as:
$H=-\sum _{ij}(A_{ij}w_{ij}-\gamma )\delta (c_{i},c_{j})$

### Understanding Potts Model resolution parameters/Resolution limit

Typically Potts models such as RB or CPM include a resolution parameter in their calculation. Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection. The resolution limit problem is that, for some graphs, maximizing modularity may cause substructures of a graph to merge and become a single community and thus smaller structures are lost. These resolution parameters allow modularity adjacent methods to be modified to suit the requirements of the user applying the Leiden algorithm to account for small substructures at a certain granularity.
The figure on the right illustrates why resolution can be a helpful parameter when using modularity based quality metrics. In the first graph, modularity only captures the large scale structures of the graph; however, in the second example, a more granular quality metric could potentially detect all substructures in a graph.

## Algorithm

The Leiden algorithm starts with a graph of disorganized nodes (a) and sorts it by partitioning them to maximize modularity (the difference in quality between the generated partition and a hypothetical randomized partition of communities). The method it uses is similar to the Louvain algorithm, except that after moving each node it also considers that node's neighbors that are not already in the community it was placed in. This process results in our first partition (b), also referred to as ${\mathcal {P}}$. Then the algorithm refines this partition by first placing each node into its own individual community and then moving them from one community to another to maximize modularity. It does this iteratively until each node has been visited and moved, and each community has been refined - this creates partition (c), which is the initial partition of ${\mathcal {P}}_{\text{refined}}$. Then an aggregate network (d) is created by turning each community into a node. ${\mathcal {P}}_{\text{refined}}$ is used as the basis for the aggregate network while ${\mathcal {P}}$ is used to create its initial partition. Because we use the original partition ${\mathcal {P}}$ in this step, we must retain it so that it can be used in future iterations. These steps together form the first iteration of the algorithm.
In subsequent iterations, the nodes of the aggregate network (which each represent a community) are once again placed into their own individual communities and then sorted according to modularity to form a new ${\mathcal {P}}_{\text{refined}}$, forming (e) in the above graphic. In the case depicted by the graph, the nodes were already sorted optimally, so no change took place, resulting in partition (f). Then the nodes of partition (f) would once again be aggregated using the same method as before, with the original partition ${\mathcal {P}}$ still being retained. This portion of the algorithm repeats until each aggregate node is in its own individual network; this means that no further improvements can be made.
The Leiden algorithm consists of three main steps: local moving of nodes, refinement of the partition, and aggregation of the network based on the refined partition. All of the functions in the following steps are called using our main function Leiden, depicted below: The Fast Louvain method is borrowed by the authors of Leiden from "A Simple Acceleration Method for the Louvain Algorithm".
Step 1: Local Moving of Nodes
First, we move the nodes from ${\mathcal {P}}$ into neighboring communities to maximize modularity (the difference in quality between the generated partition and a hypothetical randomized partition of communities). In the above image, our initial collection of unsorted nodes is represented by the graph on the left, with each node's unique color representing that they do not belong to a community yet. The graph on the right is a representation of this step's result, the sorted graph ${\mathcal {P}}$; note how the nodes have all been moved into one of three communities, as represented by the nodes' colors (red, blue, and green).
Step 2: Refinement of the Partition
Next, each node in the network is assigned to its own individual community and then moved them from one community to another to maximize modularity. This occurs iteratively until each node has been visited and moved, and is very similar to the creation of ${\mathcal {P}}$ except that each community is refined after a node is moved. The result is our initial partition for ${\mathcal {P}}_{\text{refined}}$, as shown on the right. Note that we're also keeping track of the communities from ${\mathcal {P}}$, which are represented by the colored backgrounds behind the nodes.
Step 3: Aggregation of the Network
We then convert each community in ${\mathcal {P}}_{\text{refined}}$ into a single node. Note how, as is depicted in the above image, the communities of ${\mathcal {P}}$ are used to sort these aggregate nodes after their creation.
We repeat these steps until each community contains only one node, with each of these nodes representing an aggregate of nodes from the original network that are strongly connected with each other.

## Limitations

The Leiden algorithm does a great job of creating a quality partition which places nodes into distinct communities. However, Leiden creates a hard partition, meaning nodes can belong to only one community. In many networks such as social networks, nodes may belong to multiple communities and in this case other methods may be preferred.
Leiden is more efficient than Louvain, but in the case of massive graphs may result in extended processing times. Recent advancements have boosted the speed using a "parallel multicore implementation of the Leiden algorithm".
The Leiden algorithm does much to overcome the resolution limit problem. However, there is still the possibility that small substructures can be missed in certain cases. The selection of the gamma parameter is crucial to ensure that these structures are not missed, as it can vary significantly from one graph to the next.