Leiden algorithm

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.

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.

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

The image depicts 2 separate community interpretations of the graph shown. The first graph shows 2 separate communities(1 blue, 1 red) that attempt to maximize modularity. The second graph interpretation shows 3 communities(1 blue, 1 red, 1 green) that show a more accurate representation of the substructures within the graph

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

A graph depicting the steps of the Leiden 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:

function Leiden(Graph G, Partition P)
  do
    # move nodes into their own individual communities
    P = MoveNodes(G, P)
    # stop when each community contains only a single node
    done = (|P| == |V(G)|)
    if not done then:
      # refine the partition P
      P_refined = RefinePartition(G, P)
      # create an aggregate graph where each partition is a node
      G = AggregateGraph(G, P_refined)
      # but retain the original partition P
      P = {{v | v ⊆ C, v ∈ V(G)} | C ∈ P}
    end if
  while not done
  return flat * P
end function

Step 1 of the Leiden algorithm (local moving of nodes).

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).

function MoveNodes(Graph G, Partition P)
  Q = Queue(V(G))
  do
    # determine next node to visit
    v = Q.remove()
    # use modularity score to determine best community for node v
    # note that C ∈ P ∪ ∅
    C′ = argmax(∆Hp(v -> C))
    # only perform movements that yield a positive modularity score
    if ∆Hp(v -> C′) > 0 then
      v -> C′
      # identify neighboring nodes that aren't in community C'
      N = {u | (u,v) ∈ E(G), u !∈ C′}
      # add these neighbors to the queue to make sure they get visited
      Q.add(N −Q)
    end if
  # end the loop if there are no nodes left to visit
  while Q != ∅
  return P
end function

Step 2 of the Leiden algorithm (refinement of the partition).

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 each community has been refined. This forms our initial partition for ${\mathcal {P}}_{\text{refined}}$.

function RefinePartition(Graph G, Partition P)
  P_refined = SingletonPartition(G)
  for C ∈ P do
    P_refined = MergeSubset(G, P_refined, C)
  end for
  return P_refined
end function

function SingletonPartition(G)
  # assign each node to its own community
  return {{v} | v ∈ V(G)}
end function

function MergeSubset(Graph G, Partition P, Subset S)
  # consider only nodes that are well-connected within subset S
  R = {v |v ∈S,E(v,S −v) ≥γ∥v∥·(∥S∥−∥v∥)}
  # visit nodes in random order
  for v ∈ R do
    # only consider nodes that haven't been merged yet
    if v in singleton community then
      # only consider well-connected communities
      T = {C | C ∈ P, C ⊆ S, E(C, S−C) ≥γ∥C∥·(∥S∥−∥C∥)}
      # choose random community C'
      Pr(C' = C) ~ {exp( (1/θ)∆Hp(v → C)) if ∆Hp(v → C) ≥ 0, otherwise 0} for C ∈ T
      # move v to community C'
      v → C'
    end if
  end for
  return P
end function

Step 3 of the Leiden algorithm (aggregation of the network).

Step 3: Aggregation of the Network

We then convert each community in ${\mathcal {P}}_{\text{refined}}$ into a single node.

function AggregateGraph(Graph G, Partition P)
  # communities become nodes in aggregate graph
  V = P
  # E is a multiset
  E = {(C, D) | (u, v) ∈ E(G), u ∈ C ∈ P, v ∈ D ∈ P}
  return Graph(V, E)
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.