# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 2 Literature  
This section provides an overview of widely used graph clustering algorithms, encompassing both partitioning and overlapping clustering approaches. In [16], an extensive exploration is conducted on the categorization, underlying principles, and parameterization techniques of partitioning clustering algorithms. This exploration provides valuable insights into the intricate characteristics of these algorithms. Overall, this section contributes to a fundamental understanding of the current state-of-the-art graph clustering algorithms. In the realm of graph clustering, a multitude of state-of-the-art algorithms have emerged to address the identification of cohesive communities or subgraphs within complex networks or graphs. Among them, the Girvan-Newman (GN) algorithm [12] utilizes edge-betweenness to find clusters in complex networks. By creating a hierarchical dendrogram, the algorithm enables modularity analysis to identify the optimal level cut. The Louvain algorithm [13], known for its multilevel clustering approach, optimizes modularity through local node movements and network aggregation. However, the Louvain algorithm has limitations in identifying small communities. To address the issue of poorly connected clusters, the Leiden algorithm [17] enhances the Louvain method by employing fast local moves and random neighbor moves. This enhancement ensures the formation of internally connected clusters and leads to a stable partition. Fluid communities is another example of a clustering algorithm that partitions a graph into communities using virtual fluid and has found applications in various domains [18]. It also provides an adjustable parameter for cluster customization. The spectral method leverages the power of eigenvalues derived from special matrices to improve the performance of cluster determination. It outperforms conventional methods such as k-means and enables a more robust analysis of complex networks [19; 20]. Users may specify the desired number of clusters (\(k\)), or the algorithm may arbitrarily determine this value. The expectation maximization (EM) algorithm [21] embraces a model-based approach by estimating essential parameters through probability distributions. Furthermore, it provides users with the ability to define the optimal number of clusters (\(k\)) and adjust additional parameters, including maximal iterations and convergence criteria. The fast greedy algorithm is a notable example of a scalable and efficient agglomerative hierarchical clustering method [22; 23]. It operates without the need for user-specified parameters and takes advantage of optimized data structures and strategic optimization shortcuts. The InfoMap algorithm adopts information theory principles [24; 25] by employing random walks to analyze information flow and partition the network into modules. It also optimizes the transmission rate together with minimum description length to quantify clustering quality. Similar to InfoMap, the label propagation algorithm (LPA) is another approach that avoids parameter specification by iteratively assigning node labels based on neighbors to achieve clustering [26]. To address the shortcomings of randomness issues, extended versions of LPAs, such as MemLPA and LPA-MNI, have been proposed to enhance the performance [27; 28]. The Walktrap algorithm adopts a hierarchical approach through random walks and merging neighboring clusters. It incorporates a parameter 't' to facilitate practical applications in its attempt to optimize the performance [29]. The spinglass approach [30; 31], inspired by statistical mechanics, utilizes the 'Potts model' to connect nodes sharing the same spin state and employs advanced simulated annealing techniques for resource-efficient cluster identification. The leading eigenvector capitalizes on modularity maximization by computing the leading eigenvector of the modularity matrix in partitioning the graph [32].