# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
The clustering outcomes resulting from the partitioning clustering of eight real-world networks are summarized in Table 2, while the results of overlapping clustering are detailed in Table 3.

Furthermore, visual representations illustrate clusters from both types of clustering within a confined space on two distinct networks: Zachary's Karate Club (ZKC) and the \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Network** & \(V\) & \(E\) & \(max_{deg}(E)\) & \(min_{deg}(E)\) & \(Avg_{deg}(\mathcal{G},E)\) & \(\sigma(E)\) \\ \hline Zachary’s Karate Club (ZKC) & 34 & 78 & 28 & 5 & 15 & 5 \\ \hline Aves-Weaver Social (AWS) & 42 & 152 & 43 & 3 & 20 & 9 \\ \hline Dolphins Interaction (DI) & 62 & 159 & 22 & 3 & 13 & 3 \\ \hline Les Misérables (LM) & 77 & 254 & 57 & 2 & 23 & 10 \\ \hline Political Books (PB) & 105 & 441 & 48 & 4 & 22 & 8 \\ \hline American College Football (ACF) & 115 & 613 & 23 & 15 & 20 & 1 \\ \hline Facebook Pages Food (FBPF) & 620 & 2102 & 147 & 2 & 14 & 13 \\ \hline US-Grid Power (USGP) & 4941 & 6594 & 28 & 2 & 7 & 3 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Characteristics of selected networks. US-Grid Power (USGP) network. These networks were chosen for their diverse structural properties. Despite its small scale, ZKC demonstrates dense interconnectivity, characterized by an average degree edge \(Avg_{dog}(G,E))\) of 15, allowing for a distinct analysis of the determined clusters. In contrast, the USGP, being the largest network, exhibits sparse connectivity, reflected in an average degree (\(Avg_{dog}(G,E)\)) of 7. ### Partitioning Clustering Results

In this subsection, the outcomes of partitioning clustering are investigated through the utilization of two user-specified density settings: 0.4 and 0.6. The analysis presents an exploration of the inherent characteristics exhibited by the resultant clusters. This exploration includes several key facets, including the determination of the number of clusters (\(c_{k}\)) formed at each density configuration, in conjunction with the computation of the corresponding average relative density (\(Avg_{dog}(C)\)) for a set of clusters. Furthermore, the identification of unclustered nodes is also presented for each dataset, thus contributing to a comprehensive understanding of the implications arising from the clustering outcomes. This information reveals the influence that the topology and characteristics of each network have on the formation of clusters. The results presented in Table 2 reveal a consistent density pattern for a density parameter of 0.4. Under this condition, the average relative density closely corresponds to the user-specified value. This alignment indicates a substantial portion of clusters adhering to the intended density criterion. It is worth noting that the number of clusters varies across different density settings and graph structures. Conversely, when a higher density of 0.6 is applied, certain networks exhibit slightly lower average relative densities compared to the desired density. This phenomenon is indicative of clusters with higher cohesion, resulting in fewer clusters and the formation of larger, densely populated clusters. In Figure 5(a),b, the results of partitioning clustering for the Zachary network are depicted at density settings of 0.4 and 0.6, respectively. These visualizations employ different colors to distinguish distinct clusters. Node labels are formatted as follows: the first number represents the node, and the second number indicates the cluster (e.g., (16-2) denotes that node 16 belongs to cluster 2). Additionally, unclustered nodes are represented in gray. Figure 5(a) reveals the presence of two clusters with densities that precisely match the user-specified value. Despite significant variations in node sizes among these clusters, their similar densities reveal an interesting feature of the proposed approach as they emphasize the importance of density in cluster separation.