# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
Traditional metrics like average embeddedness, FOMD, conductance, and coverage are designed for nonoverlapping scenarios, thus encountering limitations in these cases. The metrics values for Zachary's Karate Club and Facebook Pages Food are good examples of the unsuitability for their uses in overlapping clustering. This identifies the need for more suitable metrics for such clustering. Referring to Table 7, similarly, in the external quality evaluation of overlapping outcomes, the cut ratio metric once again emerges as the most favorable. In overlapping clustering, clusters have the potential to expand up to the desired density, resulting in larger clusters in terms of nodes. Therefore, the denominator in the cut ratio calculation increases, leading to relatively lower values for this metric compared to non-overlapping scenarios. Note that each metric was invented with a particular objective in mind. All internal connectivity metrics have similar intentions, and the same can be said for all external connectivity metrics. In overlapping clustering, these metrics were not supposed to be used to assess the performance of clustering; hence, their values can be out of range (as in Table 6). Finding suitable external connectivity metrics is beyond the scope of this work. Careful analysis of the use of these metrics reveals interesting facts. Internal connectivity metrics yield relatively poor for both partitioning and overlapping clustering, while the opposite can be said for external connectivity metrics. It can be argued that, for this particular work, current metrics, which exclusively consider either one or both types of connections, are inappropriate for the clustering process. This hampers a meaningful evaluation of the proposed method. An appropriate metric known as the mean relative density deviation coefficient [16] is probably the best metric for this work as it is meant for a similar objective. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**Cov**} & \multicolumn{2}{c}{**Avg-Embed**} & \multicolumn{2}{c}{**Avg-FOMD**} & \multicolumn{2}{c}{**Avg-TPR**} & \multicolumn{2}{c}{**Avg-IED**} \\ \cline{2-11}  & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** \\ \hline Zachary’s Karate Club & 1.4 & 2 & 0.63 & 0.79 & 0.30 & 0.35 & **0.75** & **0.89** & 0.25 & 0.22 \\ \hline Aves-Weaver Social & 2.1 & 3.6 & 0.61 & 0.76 & 0.21 & 0.32 & **0.94** & **0.98** & 0.44 & 0.41 \\ \hline Dolphins Interaction & 2.0 & 2.4 & 0.62 & 0.75 & 0.34 & 0.40 & **0.83** & **0.89** & 0.32 & 0.17 \\ \hline Les Misérables & 1.3 & 2.8 & **0.64** & 0.78 & 0.24 & 0.41 & **0.64** & **0.94** & 0.44 & 0.26 \\ \hline Political Books & 2.1 & 4.3 & 0.58 & 0.74 & 0.41 & 0.45 & **0.94** & **0.97** & 0.24 & 0.17 \\ \hline American College Football & 2.6 & 4.9 & 0.57 & 0.75 & 0.39 & 0.37 & **0.89** & **0.95** & 0.17 & 0.10 \\ \hline Facebook Pages Food & 10.5 & 14.7 & 0.64 & **0.78** & 0.38 & 0.43 & **0.71** & **0.78** & 0.35 & 0.17 \\ \hline US-Grid Power & **0.82** & 2.7 & 0.62 & **0.77** & 0.25 & 0.33 & 0.12 & 0.15 & 0.54 & 0.25 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Overlapping resultant clusters’ internal connectivity evaluation under \(U(\delta_{r})\) 0.4 and 0.6. Best results are shown in bold. ### Mean Relative Density Deviation Coefficient (MRDDC) Metric

As explored earlier, it is arguable that prevailing quality metrics, primarily focusing on singular or combined connectivity aspects, might lack adequacy for assessing the density proximity of clusters comprehensively. The inappropriate nature of the existing metrics to comprehensively assess both partitioning and overlapping clustering methods, especially when aiming for specific cluster densities, necessitates an appropriate metric. The MRDDC is the suitable metric to assess the proposed approach as it is introduced to assess the performance of clustering where resulting clusters should be of a required density. MRDDC can be determined by Equation (7) below.