# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 1 Introduction  
The rapid increase in the volume of data and the popularity of artificial intelligence (AI) over the last few decades have led to the emergence of the popular fields known as data science and knowledge discovery. These fields provide techniques aimed at uncovering hidden structures and useful patterns within the available information. In its simplest terms, clustering is a technique that separates information into distinct groups in which intra-similarities are maximized while inter-similarities are minimized [1]. When information can be represented as a graph or a network, then graph clustering, a sub-field of clustering, has a direct application by analyzing the connectivity and information within nodes and edges to discover intrinsic knowledge hidden within the underlying structure [2]. In almost all domains of science, graph clustering serves a variety of objectives, such as extracting similar interests of communities within a large social network [2, 3]. In transportation networks, it is applied in optimizing routes and traffic flow [4]. Bioinformatics is another field where the application of graph clustering is prolific. Identifying functional modules of genes or proteins is such an example [5]. Other application areas include image segmentation [6] and personalized recommendations in a recommendation system [7, 8] etc. Graph clustering is an NP-class problem [9] that can be classified into three distinct categories, partitioning, overlapping, and hierarchical clustering [2]. Section 3 elaborateson this further. In addition, numerous graph clustering algorithms have been proposed according to their diverse objectives. A few well-known techniques include k-means [10], DBSCAN [11], Girvan-Newman [12], Louvain [13], and numerous others. These algorithms can be parameter-free (i.e., preset to default) or parameterizable (i.e., allowing users to specify some parametric values). The scope of these parameters spans several facets; these are the cluster quantity, minimum neighboring points, the resolution parameter, regularization parameter, and convergence criteria [14]. Complex algorithms, such as random walk-based and spectral clustering, require some level of expertise in graph theory and linear algebra to adjust for suitable values of their parameters. They often involve numerous iterations and experimentation and their assessment usually involves the adjusting procedure. These can render them computationally intensive, especially for extensive and intricate networks. In order to take full advantage of parameter tuning, algorithmic complexity is often associated. Apart from computational complexity, this process may result in unbalanced clusters, especially if parameters are inappropriately adjusted. In the context of density and connectivity, unbalanced clustering can lead to inefficient resource utilization and a rise in maintenance costs [15]. As stated above, graph clustering has applications in almost every domain, and, like many other areas of science, graph clustering algorithms were introduced in response to the objective(s) of their applications. Nevertheless, there remain several requirements in graph clustering that have yet to be fulfilled. One of these is the capability to cluster a graph in such a way that the resultant clusters have a comparable or identical density. This feature is useful in the deployment and administration of resources in a variety of applications, for example, if a large community is represented by a complex graph. Subcommunities can be viewed as clusters within the whole community. If they are of equal or comparable density, distribution of resources can be more efficiently completed. A network that represents communication among individuals through LINE messaging is another good example. It would be beneficial if the network could be partitioned into smaller units with similar density. This allows for an efficient deployment of resources to monitor these communities as each subcommunity is likely to require similar resources.