# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
Examining Figure 5(b) at a density setting of 0.6 reveals the emergence of two clusters characterized by both larger size and higher density. This heightened the fact that density facilitates the formation of more substantial \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{\(\epsilon_{k}\)} & \multicolumn{2}{c}{\(Avg_{dog}\) **(C)**} & \multicolumn{2}{c}{**Unclustered Nodes**} \\ \cline{2-7}  & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** \\ \hline Zachary’s Karate Club & 2 & 2 & 0.40 & 0.60 & 8 & 5 \\ \hline Aves-Weaver Social & 5 & 4 & 0.38 & 0.60 & 5 & 3 \\ \hline Dolphins Interaction & 4 & 2 & 0.40 & 0.45 & 15 & 11 \\ \hline Les Miserables & 4 & 3 & 0.40 & 0.60 & 8 & 14 \\ \hline Political Books & 3 & 5 & 0.40 & 0.40 & 4 & 5 \\ \hline American College Football & 4 & 3 & 0.30 & 0.40 & 7 & 4 \\ \hline Facebook Pages Food & 25 & 23 & 0.37 & 0.50 & 138 & 116 \\ \hline US-Grid Power & 626 & 320 & 0.40 & 0.58 & 1350 & 859 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Partitioning clustering results for \(U(\delta_{r})\) of 0.4 and 0.6.

and densely populated clusters. Importantly, this increase in density is accompanied by a notable reduction in the count of unclustered nodes. Figure 7 presents the partitioning clustering outcomes for the US-Power Grid network. Different colors represent distinct clusters, but due to the large network size and a high number of clusters, assigning a unique color to each cluster becomes challenging, leading to the repetition of colors for clusters in this scenario. Figure 7a shows the partitioning clustering results for a density of 0.4. It reveals a pattern of relatively smaller and more clusters. Figure 7b illustrates the clustering outcomes at a density of 0.6. It reveals a substantial reduction in the number of clusters by nearly half when compared to Figure 7a. This reduction highlights the emergence of larger and more densely populated clusters, a feature particularly pronounced in Figure 7b. This pattern suggests a transition towards a denser and more cohesive clustering structure, characterized by fewer and more substantial clusters. Notably, the number of unclustered nodes decreases by 64% compared to the clusters obtained at a density of 0.4. ### Overlapping Clustering Results

Table 3 summarizes the results of overlapping clustering, providing a comprehensive overview of all the networks in this study. Complementing this tabular representation, Figures 8 and 9 provide a visual depiction of the clustering outcomes of two selected networks for overlapping clustering. A comparison of overlapping clustering to partitioning clustering in Table 2 reveals that overlapping clustering results in a greater number of clusters for both values of \(U(\delta_{r})\), as evidenced by the values of \(c_{k}\). The average degree of the clusters \((\text{Avg}_{(\delta_{r})}(\mathcal{C}))\) is the same for both values of \(U(\delta_{r})\) for each network. Overall, the number of unclustered nodes is also reduced, although not for every network. These findings illustrate the characteristics of overlapping clustering. Since a node is allowed to be a member of more than one

Figure 6: Zachary’s Karate Club network partitioning clusters: (**a**) \(U(\delta_{r})=0.4\). (**b**) \(U(\delta_{r})=0.6\). cluster, more edges (or nodes) are available to be included during cluster expansion; hence, increasing the likelihood of achieving low-density deviation or a chance of achieving a cluster closer to \(U(\delta_{r})\) is relatively high. Another characteristic of overlapping clustering is that it increases the possibility of new cluster initiation points, which leads to a higher number of clusters (\(c_{k}\)). However, the topology of the network has a significant impact on the clustering results. In some networks, overlapping clustering can result in a higher number of unclustered nodes than partitioning clustering. As mentioned earlier, the proposed approach is intended for networks where clusters are not readily apparent.