# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
Additionally, a larger number of unclustered nodes may appear if a graph contains a large number of terminal nodes. Figure 8: Zachary’s Karate Club network overlapping clusters: (**a**) \(U(\delta_{r})=0.4\). (**b**) \(U(\delta_{r})=0.6\). ## 6 Clustering Process Evaluation

To assess the cohesiveness and separation within and between clusters, the clustering results are evaluated using pre-existing quality metrics. Internal connectivity metrics, such as coverage (Cov), average embeddedness (Avg-Embed), average fraction over median degree (Avg-FOMD), average triangle participation ratio (Avg-TPR), and average internal edge density (Avg-IED), are used to measure the strength of ties between nodes within clusters. Coverage measures the proportion of internal edges to the total number of graph edges [65], indicating how well-connected nodes are within clusters. Average embeddedness measures the ratio of internal node degrees to total node degrees, which indicates how well-connected nodes are within clusters relative to their overall connectivity in the graph [66]. FOMD measures the proportion of nodes with internal degrees exceeding the median, quantifying the number of nodes appearing in multiple clusters [66]. TPR measures the ratio of triangles within clusters to all possible triangles, reflecting cluster density [67; 68]. Average internal edge density measures the density of edges within clusters, determining the subgraph cohesion of clusters. Overall, the internal connectivity metrics provide a comprehensive assessment of how well-connected nodes are within clusters [69]. Similarly, external connectivity is another important aspect of clustering as it quantifies the interactions beyond the cluster boundaries. These metrics together provide a comprehensive view of clustering effectiveness, revealing intricate connectivity patterns from clusters to the surrounding graph. The cut ratio metric addresses the challenge of edge distribution between different clusters [70; 71]. Expansion quantifies external edges per node in a cluster, revealing cluster compactness. Conductance is a widely used metric that captures both internal and external connectivity [65]. Normalized cut partitions the graph for cohesive clusters with weak intercluster links [72]. Flake-ODF (out degree fraction) assesses cluster external connectivity by measuring nodes within the cluster that have more edges directed outside the cluster than within it [72]. Collectively, these metrics provide a robust framework for assessing the effectiveness of clustering methods and encompass diverse aspects of connectivity. It is worth noting that these metrics range from 0 to 1. For internal connectivity metrics, values approaching 1 indicate better clustering results and vice versa for external connectivity metrics. In the following subsection, the evaluation Tables 4 and 5 emphasize the optimal values by using bold formatting. However, in Table 6, the coverage metric values are not highlighted. This is intentional as values exceeding the metric range do not represent optimal conditions. This is particularly observed due to the nature of overlapping

Figure 9: US-Grid Power network overlapping clusters: (**a**) \(U(\delta_{r})=0.4\). (**b**) \(U(\delta_{r})=0.6\). clustering. Tables 4-7 are respective to rows (i.e., which metric yields the best value for each network under two density conditions). The highlights in Tables 8 and 9 are respective to columns (i.e., which network yields the best value for MRDCC). In the comparison between clique-based and edge-based approaches, Tables 10 and 11 highlight optimal values with respect to rows. ### Partitioning Clustering Outcomes Evaluation through Pre-Existing Quality Metrics

Referring to Table 4, among the existing metrics, the average embeddedness metric consistently yields higher values compared to other internal connectivity metrics across various networks and density variations.