Leiden algorithm
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.
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[1]) and a graph aggregation step.
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.
How communities are partitioned is an integral part on the Leiden algorithm.
Additionally, many of these metrics contain parameters of their own that can change the outcome of their communities.
Modularity is a highly used quality metric for assessing how well a set of communities partition a graph.
One of the most well used metrics for the Leiden algorithm is the Reichardt Bornholdt Potts Model (RB).
[3] This model is used by default in most mainstream Leiden algorithm libraries under the name RBConfigurationVertexPartition.
This model is defined by the following quality function for an adjacency matrix, A, as:[4]
where: Another metric similar to RB, is the Constant Potts Model (CPM).
Typically Potts models such as RB or CPM include a resolution parameter in their calculation.
[3][6] Potts models are introduced as a response to the resolution limit problem that is present in modularity maximization based community detection.
[7] 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.
Then an aggregate network (d) is created by turning each community into a node.
In the case depicted by the graph, the nodes were already sorted optimally, so no change took place, resulting in partition (f).
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".
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.
This occurs iteratively until each node has been visited and moved, and is very similar to the creation of
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.
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".
[9] The Leiden algorithm does much to overcome the resolution limit problem.
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.
