# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
The proposed approach in this work yields slightly better performance in almost all networks for both values of \(U(\delta_{r})\). The MRDCC of the American College Football is slightly less than those of [16]. Again, this is likely due to the highest average node degree, as discussed in the earlier subsection (results in Table 8). Ideally, good graph clustering, regardless of type, ought to cover all the nodes in the graph/network (i.e., every node belongs to, at least, a cluster) and no node remains unclustered. In practice, this cannot always be guaranteed, especially when a resultant cluster is subjected to certain constraint(s). Also, the topology may dictate the results of clustering. Referring to Table 11 reveals the comparison of both approaches concerning the number of unclustered nodes. All the edge-based methods in this work are superior to the clique-based approach, except the American College Football for \(U(\delta_{r})\) of 0.6. For a large network such as US-Grid Power, the proposed edge-based method in this work is preferable. It is worth noting, before clustering, that the proposed edge-based method is also computationally more efficient as the determination of 'edge degree' for all edges requires less computation time than the determination of all cliques hidden in the network. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{\(U(\delta_{r})=0.4\)} & \multicolumn{2}{c}{\(U(\delta_{r})=0.6\)} \\ \cline{2-5}  & **Edge-Based** & **Clique-Based** & **Edge-Based** & **Clique-Based** \\ \hline Zachary’s Karate & **1.00** & 0.90 & 0.97 & **1.00** \\ \hline Aves-Weaver & **0.92** & 0.86 & **0.95** & 0.84 \\ \hline Dolphins Interaction & 0.91 & **1.00** & 0.80 & **0.91** \\ \hline Les Misérables & **1.00** & **1.00** & 0.99 & **1.00** \\ \hline Political Books & **1.00** & 0.89 & 0.72 & **0.76** \\ \hline American College Football & 0.88 & **0.92** & 0.65 & **0.95** \\ \hline Facebook Pages Food & **0.89** & 0.88 & 0.78 & **0.94** \\ \hline US-Grid Power & **0.95** & 0.90 & **0.93** & 0.90 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Comparison with respect to mean relative density deviation coefficient (MRDDC) metric. Best results are shown in bold. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{\(U(\delta_{r})=0.4\)} & \multicolumn{2}{c}{\(U(\delta_{r})=0.6\)} \\ \cline{2-5}  & **Edge-Based** & **Clique-Based** & **Edge-Based** & **Clique-Based** \\ \hline Zachary’s Karate & **8** & 9 & **5** & **5** \\ \hline Aves-Weaver & **3** & 8 & **3** & 5 \\ \hline Dolphins Interaction & **11** & 19 & **11** & 17 \\ \hline Les Misérables & **8** & 25 & **14** & 20 \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Comparison with respect to number of unclustered nodes. Best results (i.e., lower number of unclustered nodes) are shown in bold. useful in some applications. On the contrary, if the network is relatively dense, specifying a low value of \(U(\delta_{r})\) can lead to the same small-size clusters. In determining standard specifications for the user-specified density \(U(\delta_{r})\), this study reveals crucial considerations in guiding users effectively when applying \(U(\delta_{r})\) to diverse network analyses. * Density Specification: A fundamental standard proposed is the range within which the \(U(\delta_{r})\) parameter should fall. Values beyond this range are deemed irrelevant in the context of the study, ensuring a valid and coherent parameter threshold. * Topology-Dependent Specification: The specification of the \(U(\delta_{r})\) parameter is intricately tied to the topology of the network under analysis. Contrary to conventional assumptions in density contexts, where higher density often corresponds to more clusters, this study reveals that this may not universally hold. Instead, the appropriate value for \(U(\delta_{r})\) is highly dependent on the specific characteristics of the network.