## 3 Graph Clustering Methods
### Louvain and Modularity  
Modularity serves as an assessment of how effectively the nodes within a graph are divided into distinct partitions. This concept suggests a prevalence of connections within each partition, known as intra-community edges, contrasted with a lower occurrence of connections between different partitions, termed inter-community edges. Essentially, it indicates that nodes within the same community are more strongly connected to each other compared to nodes in different communities [13]. The modularity score evaluates, for a set of nodes, the ratio of observed edges to expected edges (based on a comparable graph with edges distributed randomly, akin to the Erdos-Renyi model [24]). If the observed edges exceed the expected count, it indicates the likelihood of a community structure. This score quantifies the partitioning quality of a graph using the following formula:  
\[Q_{\text{modularity}}=\frac{1}{2m}\sum_{i,j}\bigl{(}A_{ij}-P_{ij}\bigr{)} \delta\bigl{(}C_{i},C_{j}\bigr{)} \tag{1}\]  
Here, \(A_{ij}\) represents the value at position \(ij\) in the adjacency matrix. \(m\) denotes the total number of edges, while \(2m\) signifies the total count of half-edges. The symbol \(\delta\) refers to the Kronecker delta: \(\delta(C_{i},C_{j})=1\) if nodes \(i\) and \(j\) belong to the same community \(C\) (i.e., \(C_{i}=C_{j}\)), and \(\delta(C_{i},C_{j})=0\) otherwise. \(P_{ij}\) represents the probability of the number of connections between nodes \(i\) and \(j\) under a null Erdos-Renyi model, which generates a uniformly connected graph. Consequently, maximizing the modularity \(Q\) involves identifying sets of nodes exhibiting an unusually high level of connectedness.  
Modularity serves as the foundational principle for extracting communities within graphs, and the Louvain method [14] stands out for its efficacy, especially when dealing with large datasets.  
This method operates hierarchically, where in the initial phase, it identifies small communities through local optimization of modularity for each node. Subsequently, nodes within the same community are amalgamated into a single node. This process is iteratively repeated on the updated network until no further increase in modularity is achievable (Figure 2 [14]).  
Figure 2: Visualization of the steps of Louvain algorithm.  
Unlike the Louvain algorithm, which merges communities at each level, the Leiden algorithm [44] primarily focuses on splitting and merging clusters at each level. As a result, it ensures the formation of more well-connected clusters. In comparison to the Louvain algorithm, the Leiden algorithm incorporates a fast local move approach, enabling the movement of one or more nodes from one cluster to another to enhance the quality of clusters during each iteration of community detection. Nodes are selected for movement only if they are considered unstable. This distinction improves the runtime efficiency of the Leiden algorithm compared to the Louvain method. Additionally, the Leiden algorithm addresses a major inefficiency of the Louvain method, which occasionally generates poorly connected nodes as a community and may result in a fragmented network community.