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". function Leiden_community_detection(Graph G, Partition P) do P = fast_louvain_move_nodes(G, P) /* Call the function to move the nodes to communities.(more details in function below). */ done = (|P| == |V(G)|) /* If the number of partitions in P equals the number of nodes in G, then set done flag to True to end do-while loop, as this will mean that each node has been aggregated into its own community. */ if not done P_refined = get_p_refined(G, P) /* This is a crucial part of what separates Leiden from Louvain, as this refinement of the partition enforces that only nodes that are well connected within their community are considered to be moved out of the community. (more detail in function refine_partition_subset below). */ G = aggregate_graph(G, P_refined) /* Aggregates communities into single nodes for next iteration (details in function below). */ P = {{v | v ⊆ C, v ∈ V (G)} | C ∈ P} /* This line essentially takes nodes from the communities in P and breaks them down so that each node is treated as its own singleton community (community made up of one node). */ end if while not done return flattened(P) /* Return final partition where all nodes of G are listed in one community each. */ end function
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). function fast_louvain_move_nodes(Graph G, Partition P) Q = queue(V(G)) /* Place all of the nodes of G into a queue to ensure that they are all visited. */ while Q not empty v = Q.pop_front() /* Select the first node from the queue to visit. */ C_prime = arg maxC∈P∪∅ ∆HP(v → C) /* Set C_prime to be the community in P or the empty set (no community) that provides the maximum increase in the Quality function H when node v is moved into that community. */ if ∆HP(v → C_prime) > 0 /* Only look at moving nodes that will result in a positive change in the quality function. */ v → C_prime /* Move node v to community C_prime */ N = {u | (u, v) ∈ E(G), u !∈ C_prime} /* Create a set N of nodes that are direct neighbors of v but are not in the community C_prime. */ Q.add(N - Q) /* Add all of the nodes from N to the queue, unless they are already in Q. */ end if return P /* Return the updated partition. */ end function
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. function get_p_refined(Graph G, Partition P) P_refined = get_singleton_partition(G) /* Assign each node in G to a singleton community (a community by itself). */ for C ∈ P P_refined = refine_partition_subset(G, P_refined, C) /* Refine partition for each of the communities in P_refined. */ end for return P_refined /* return newly refined partition. */ function refine_partition_subset(Graph G, Partition P, Subset S) R = {v | v ∈ S, E(v, S − v) ≥ γ * degree(v) * (degree(S) − degree(v))} /* For node v, which is a member of subset S, check if E(v, S-v) (the edges of v connected to other members of the community S, excluding v itself) are above a certain scaling factor. degree(v) is the degree of node v and degree(S) is the total degree of the nodes in the subset S. This statement essentially requires that if v is removed from the subset, the community will remain intact. */ for v ∈ R if v in singleton_community /* If node v is in a singleton community, meaning it is the only node. */ T = {C | C ∈ P, C ⊆ S, E(C, S − C) ≥ γ * degree(C) · (degree(S) − degree(C)} /* Create a set T of communities where E(C, S - C) (the edges between community C and subset S, excluding edges between community C and itself) is greater than the threshold. The threshold here is γ * degree(C) · (degree(S) − degree(C). */ Pr(C_prime = C) ~ exp(1/θ ∆HP(v → C) if ∆HP(v → C) ≥ 0 0 otherwise for C ∈ T /* If moving the node v to C_prime changes the quality function in the positive direction, set the probability that the community of v to exp(1/θ * ∆HP(v → C)) else set it to 0 for all of the communities in T. */ v → C_prime /* Move node v into a random C_prime community with a positive probability. */ end if end for return P /* return refined partition */ end function
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. function aggregate_graph(Graph G, Partition P) V = P /* Set communities of P as individual nodes of the graph. */ E = {(C, D) | (u, v) ∈ E(G), u ∈ C ∈ P, v ∈ D ∈ P} /* If u is a member of subset C of P, and v is a member subset D of P and u and v share an edge in E(G), then we add a connection between C and D in the new graph. */ return Graph(V, E) /* Return the new graph's nodes and edges. */ end function function get_singleton_partition(Graph G) return {{v} | v ∈ V (G)} /* This is the function where we assign each node in G to a singleton community (a community by itself). */ end function 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==