# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
\[\text{MRDDC}=1-\frac{1}{k}\sum_{c_{i}=1}^{c_{k}}\left|\frac{U(\delta_{r})- \delta_{r}(c_{i})}{U(\delta_{r})}\right| \tag{7}\]

where \(\delta_{r}(c_{i})\) signifies the density of each individual cluster \(c_{i}\), and \(k\) denotes the total number of clusters. In obtaining a cluster with relative density \((\delta_{r})\) the same as the user-specified density \(U(\delta_{r})\), this implies that the deviation is zero (i.e., \(U(\delta_{r})-c_{i}(\delta_{r})\) is zero). In a situation where MRDCC is 1, this implies that the cluster is just a single node (which should not be considered a cluster). By dividing this deviation by \(U(\delta_{r})\) and taking the absolute value, this metric normalized to a range between 0 and 1. Therefore, the average deviation \(\frac{1}{k}\sum_{i=1}^{k}\left|\frac{U(\delta_{r})-\delta_{r}(c_{i})}{U(\delta _{r})}\right|\) also falls within the range of zero to one. This average deviation has a value of 0 for the best scenario and 1 for the worst. This appears unintuitive as most researchers tend to associate the value of 1 with the best result and 0 with the worst. To make this metric intuitive, MRDCC is derived by the value of 1 subtracted by the average deviation (as expressed in Equation (7)). In summary, MRDCC quantifies the proximity of the resulting clusters to the \(U(\delta_{r})\), thereby reflecting the effectiveness of the graph clustering process. ### Partitioning and Overlapping Outcomes Evaluation Using MRDDC Metric

Table 8 reveals the performance of the proposed partitioning clustering approach using the MRDDC metric. As stated in the previous subsection, it is a more appropriate metric for the validation of this work. Among the datasets evaluated, the American College Football network exhibits the lowest values for both values of \(U(\delta_{r})\). This may be attributed to the fact that it possesses the highest average node degree of 20 (as shown in Table 1), reflecting its high average degree of 10.8. This leads to certain clusters characterized by heightened external connectivity and, therefore, yields lower values of MRDDC. This is another piece of evidence that the topology of a network can influence partitioning clustering significantly. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**Conductance**} & \multicolumn{2}{c}{**Cut Ratio**} & \multicolumn{2}{c}{**Normalized Cut**} & \multicolumn{2}{c}{**Flake-ODF**} \\ \cline{2-7}  & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** & **0.4** & **0.6** \\ \hline Zachary’s Karate Club & 0.41 & 0.23 & **0.11** & 0.08 & 0.62 & 0.47 & 0.13 & **0.03** \\ \hline Aves-Weaver Social & 0.40 & 0.22 & **0.13** & 0.09 & 0.59 & 0.43 & 0.18 & **0.07** \\ \hline Dolphins Interaction & 0.39 & 0.24 & **0.05** & 0.05 & 0.53 & 0.49 & 0.24 & **0.03** \\ \hline Les Misérables & 0.42 & 0.23 & **0.06** & **0.05** & 0.53 & 0.44 & 0.18 & 0.09 \\ \hline Political Books & 0.39 & 0.24 & **0.04** & **0.04** & 0.54 & 0.42 & 0.21 & 0.07 \\ \hline American College Football & 0.42 & 0.25 & **0.06** & **0.05** & 0.58 & 0.49 & 0.33 & 0.11 \\ \hline Facebook Pages Food & 0.40 & 0.20 & **0.00** & **0.00** & 0.50 & 0.39 & 0.18 & 0.06 \\ \hline US-Grid Power & 0.41 & 0.24 & **0.00** & **0.00** & 0.41 & 0.24 & 0.16 & 0.05 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Overlapping resultant clusters’ external connectivity evaluation under \(U(\delta_{r})\) 0.4 and 0.6. Best results are shown in bold. Similarly, Table 9 reveals the performance of the proposed overlapping clustering approach using the MRDDC metric. The results are superior to partitioning clustering. As nodes and edges can belong to more than one cluster, a cluster can, therefore, be quite dense (i.e., the number of internal edges is high).