# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
In providing valuable guidance, diverse experiments to uncover optimal specifications for the user-specified density parameter under various network scenarios may be necessary. This iterative process should also provide additional understanding for real-world network analyses. The discussion above aims to provide guidelines that acknowledge the network's nature and diverse structural characteristics. By embracing the interplay between user-specified density and network topology, users can make informed decisions that may enhance the effectiveness of the proposed approach in diverse applications. This work also emphasizes the concept of 'the right tool for the right job.' In assessing the efficiency of the clustering process, the existing metrics have proven to be inappropriate. This does not imply that they are not useful; in fact, metrics such as 'coverage' and 'conductance' are very popular and universal in graph clustering. However, information such as the number of unclustered nodes, the number of unclustered edges, and the area covered by clustering are not of real interest or very meaningful when a specific density of resultant clusters is required. Therefore, MRDCC, as suggested in this work, provides an efficient means of assessing the clustering. The proposed clustering technique is tailored for static connected graphs, and its performance may be affected in scenarios deviating from this assumed model. In the case of disconnected graphs, each subcomponent may be treated independently. As the algorithm relies on density as an input, users must be mindful of network characteristics when specifying density. For instance, in applications like resource management, users should be aware of relative density range in order to strategically set effective density values. These limitations underscore the importance of aligning the proposed approach with specific network conditions and domain expertise in its application. ## 8 Conclusions

Many real-world problems are graph-related, where information can be represented as graphs. In such cases, graph clustering has an application, especially when the objective includes dividing members into groups where intrasimilarity is high and intersimilarity is low. This allows intrinsic information hidden in each group as well as the overall composite graph to be extracted. This work is the first attempt at both partitioning and overlapping graph clustering of unweighted undirected graphs, where users can specify the required density. This is completed by means of 'Relative Density'. The proposed approach is edge-based, in which the concept of edge degree is utilized. The intended application is to cluster graphs where clusters are not so visible initially (i.e., \(\sigma(E)\) is not so high) as it will not be meaningful to demand a certain density from resultant clusters if the clustering pattern is evident from the start. In such situations, splitting the graph at appropriate places will be more meaningful, and there already exist such algorithms. Selecting a suitable user-specified density \(U(\delta_{r})\) may also require careful consideration. As discussed in the previous section, the density or sparsity of a graph is likely to guide a suitable value for \(U(\delta_{r})\). Among several metrics in graph clustering, the MRDCC is the most appropriate for assessing the clustering performance in this work as other metrics are invented with different objectives. As demonstrated in Section 6, overlapping clustering consistently outperforms partitioning clustering. Importantly, this is not entirely attributed to the algorithm presented in this work but stems from higher availability of edges to consider during the clustering expansion process. The inherent nature of overlapping clustering permits a node to belong to more than one cluster, resulting in clusters with relative density (\(\delta_{r}\)) near to or the same value as the user-specified density (\(U(\delta_{r})\)). The applications of the proposed clustering method are multifaceted.