# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
Furthermore, the goal of clustering in this work is not to ensure that every node or edge belongs to a cluster. Figure 8a,b depict the results of applying the proposed overlapping clustering algorithm to [PERSON]'s Karate Club network. Each cluster is depicted with the same color, and the blue nodes represent the overlapped area across different clusters. Two numbers are associated with each node: the node number and the number of clusters to which the node belongs, if the latter is enclosed in parentheses. If the second number is not in parentheses, it signifies that the node is not overlapped with any cluster. For example, in Figure 8a, the node with the label 3-1 belongs to cluster number 1. The node with label 1-(2) indicates that node '1' overlaps within two clusters (i.e., it is a member of two clusters). An alternative way of presenting the results is to enumerate the membership of each node. While this may

Figure 7: US-Grid Power network partitioning clusters: (**a**) \(U(\delta_{r})=0.4\). (**b**) \(U(\delta_{r})=0.6\). \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{\(c_{k}\)} & \multicolumn{2}{c}{\(Avg_{deg}\) (**C**)} & \multicolumn{2}{c}{**Unclustered Nodes**} & \multicolumn{2}{c}{**Overlaps Nodes**} \\ \cline{2-10}  & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** \\ \hline Zachary’s Karate Club & 5 & 4 & 0.4 & 0.6 & 0 & 3 & 19 & 22 \\ \hline Aves-Weaver Social & 9 & 8 & 0.4 & 0.6 & 3 & 3 & 20 & 21 \\ \hline Dolphins Interaction & 11 & 6 & 0.4 & 0.6 & 11 & 14 & 34 & 37 \\ \hline Les Misérables & 9 & 8 & 0.4 & 0.6 & 12 & 11 & 29 & 34 \\ \hline Political Books & 15 & 11 & 0.4 & 0.6 & 7 & 5 & 61 & 79 \\ \hline American College Football & 13 & 10 & 0.4 & 0.6 & 6 & 5 & 90 & 95 \\ \hline Facebook Pages Food & 89 & 70 & 0.4 & 0.6 & 149 & 125 & 273 & 333 \\ \hline US-Grid Power & 845 & 477 & 0.4 & 0.6 & 1181 & 734 & 1245 & 2509 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Overlapping clustering results of \(U(\delta_{r})\) 0.4 and 0.6.

seem useful for full comprehension at first, the detailed information of all clusters can be overwhelming and distracting from the main insights. Figure 8a,b illustrate the impact of the parameter \(U(\delta_{r})\) on the number and overlap of clusters. Figure 8a depicts five clusters, while Figure 8b exhibits four clusters, which is consistent with the previously discussed trend that a higher value of \(U(\delta_{r})\) leads to fewer clusters. Additionally, Figure 8b exhibits a noticeable increase in overlapping regions, which is attributable to the higher value of \(U(\delta_{r})\) in Figure 8b. This is because more edges are available for consideration during cluster expansion when \(U(\delta_{r})\) is higher. Figure 9a,b depict the results of applying the proposed overlapping clustering algorithm to the US-Power Grid network, a real-world sparse network. Notably, blue-colored nodes indicate overlaps, suggesting their presence in multiple clusters. However, due to the network's size, it is challenging to highlight each cluster with a distinct color and label each node with its respective cluster. Visual analysis of the results is complex; however, the overall characteristics are consistent with those observed in [PERSON]'s Karate Club network. Specifically, a larger value of \(U(\delta_{r})\) leads to fewer clusters, fewer unclustered nodes, and larger overlapping regions. In general, the proposed approach reveals that the number of clusters and the number of unclustered nodes in the result are inversely proportional to the value of \(U(\delta_{r})\), while the size of the overlapping regions is positively correlated. It is also important to note that the topology of the network can significantly influence the clustering process, both partitioning and overlapping. For example, in graphs that are densely connected in some areas, clusters may be evident, making graph clustering unnecessary.