# An Edge-Based Approach to Partitioning and Overlapping Graph Clustering with User-Specified Density
## 4 Proposed Partitioning and Overlapping Clustering Method
### Overlapping Clustering
As'relative density' is used as a means for the required density of a cluster in this work and referring to Equation (7), this reveals that the value of \(int_{dg}(c_{i})\) can be quite high, enabling the \(U(\delta_{r})\) to be satisfied more easily, especially when compared with partitioning clustering. Note also that, in overlapping clustering, the required density is less prone to the influence of the network topology than in partitioning clustering, as shown in the MRDCC of the American College Football network. ### Partitioning Clustering Comparative Analysis

There has been an attempt at clustering where users can specify the required relative density of the resultant clusters [16]. In this algorithm, a clique of size three (i.e., a triangle) is adopted as the basis of clustering. This work will be referred to as the 'clique-based' method for brevity and ease of discussion. A clique with an average degree is selected as an initial cluster. A cluster is expanded by adding adjacent cliques while relative density is monitored until its value is the same or closest to the specified density. However, only partitioning clustering was considered. Nevertheless, this 'clique-based' method merits special attention and comparison to this work. The partitioning clustering comparative analysis involves a thorough examination of two distinct approaches: the clique-based method and the proposed approach. Within this section, the analysis commences by evaluating the number of clusters generated by each approach. \begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**MRDDC Metric**} \\ \cline{2-3}  & \(\mathbf{U(\delta_{r})=0.4}\) & \(\mathbf{U(\delta_{r})=0.6}\) \\ \hline Zachary’s Karate & \(\mathbf{1.00}\) & \(0.97\) \\ \hline Aves-Weaver & \(0.92\) & \(0.95\) \\ \hline Dolphins Interaction & \(0.91\) & \(0.80\) \\ \hline Les M\&rables & \(\mathbf{1.00}\) & \(\mathbf{0.99}\) \\ \hline Political Books & \(\mathbf{1.00}\) & \(0.72\) \\ \hline American College Football & \(0.88\) & \(0.65\) \\ \hline Facebook Pages Food & \(0.89\) & \(0.78\) \\ \hline US-Grid Power & \(0.95\) & \(0.93\) \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Partitioning clustering evaluation using MRDDC metric of \(U(\delta_{r})\) \(0.4\) and \(0.6\). Best results are shown in bold. \begin{table}
\begin{tabular}{c c c} \hline \hline \multirow{2}{*}{**Network**} & \multicolumn{2}{c}{**MRDDC Metric**} \\ \cline{2-3}  & \(\mathbf{U(\delta_{r})=0.4}\) & \(\mathbf{U(\delta_{r})=0.6}\) \\ \hline Zachary’s Karate & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline Aves-Weaver & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline Dolphins Interaction & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline Les M\&rables & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline Political Books & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline American College Football & \(\mathbf{1.00}\) & \(\mathbf{1.00}\) \\ \hline Facebook Pages Food & \(0.99\) & \(0.99\) \\ \hline US-Grid Power & \(0.96\) & \(0.98\) \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Overlapping clustering evaluation using MRDDC metric of \(U(\delta_{r})\) \(0.4\) and \(0.6\). Best results are shown in bold. Subsequently, the analysis extends to the presence of unclustered nodes, shedding light on the effectiveness of each method in handling nodes that do not adhere to a particular cluster. Following this, the outcomes of both approaches are systematically evaluated, primarily focusing on density deviation as measured by the proposed metric (MRDDC). This metric provides insights into the proximity of the resultant clusters to the user-specified density. By considering these facets, a comprehensive understanding of the performance and limitations of both approaches is gained, thereby enabling informed decisions in selecting the most suitable clustering strategy for various scenarios. Table 10 reveals the comparison of the performance of both studies subjected to the MRDDC metric.