# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 5 Experiments
### Real World Data
#### 5.2.1 Clustering Quality Analysis of ADPSCAN  
The experimental results on several real-world datasets demonstrate that the ADPSCAN algorithm excels in clustering accuracy. We evaluated its performance on three datasets--Karate, Polbooks, and Dolphins--and compared the results with other clustering algorithms, including DistanceSCAN, GS*-Query, DPSCAN, FluidC, GN, and SCAN. The results are summarized in Table 2.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline  & \multicolumn{2}{c}{**Karate**} & \multicolumn{2}{c}{**Polbooks**} & \multicolumn{2}{c}{**Dolphins**} \\ \cline{2-7}
**Algorithm** & **ARI 1a ** & **NMI b ** & **ARI 1b ** & **NMI b ** & **ARI 1a ** & **NMI b ** \\ \hline ADPSCAN & **1.000** & **1.000** & 0.668 & **0.601** & **0.935** & **0.889** \\ DistanceSCAN & 0.515 & 0.502 & 0.633 & 0.531 & 0.753 & 0.608 \\ GS*-Query & 0.725 & 0.684 & 0.673 & 0.581 & 0.759 & 0.784 \\ DPSCAN & 0.882 & 0.837 & **0.695** & 0.593 & 0.586 & 0.740 \\ FluidC & 0.882 & 0.837 & 0.635 & 0.547 & 0.408 & 0.459 \\ GN & 0.882 & 0.837 & 0.680 & 0.576 & **0.935** & **0.889** \\ SCAN & 0.725 & 0.628 & 0.601 & 0.537 & 0.601 & 0.672 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Performance of different graph clustering algorithms on real-world data sets.  
On the Karate dataset, ADPSCAN outperformed the other five algorithms, achieving a perfect score of 1.000 in both ARI and NMI metrics. This indicates that ADPSCAN is highly effective in precisely delineating cluster boundaries within structurally simple and well-defined networks. Figure 6(a) illustrates the clustering results of ADPSCAN on the Karate dataset, successfully grouping the data into two clusters, which further validates the algorithm's effectiveness.  
In the Polbooks dataset, ADPSCAN achieved an NMI score of 0.601, outperforming other compared algorithms. Although the ARI score is slightly lower than that of DPSCAN (0.668 vs. 0.695), this discrepancy can be attributed to the different focuses of the ARI and NMI metrics. ARI emphasizes accurately recovering the true group boundaries within the dataset, while NMI assesses the amount of shared information between the algorithmically identified groups and the true groups. The presence of nodes connecting multiple clusters in the Polbooks dataset contributes to the slight decrease in ARI score.  
For the Dolphins dataset, ADPSCAN achieved the highest values for both ARI (0.935) and NMI (0.889), indicating exceptional performance in capturing the true clustering structure within biologically influenced complex networks. Figure 6(b) presents the clustering results of ADPSCAN on the Dolphins dataset, where the algorithm accurately identifies the majority of dolphins in their respective clusters.  
Overall, the observation that ADPSCAN consistently achieves optimal NMI and ARI scores can be attributed to two key components of its design. The first component is the adaptive density peak selection module, this module accurately identifies potential cluster centers without requiring manual input, thereby ensuring the accuracy of clustering. Additionally, the second component is the noise re-clustering module,the high clustering quality of ADPSCAN is further enhanced by its ability to re-cluster noise points. By computing the distance-based structural similarity between noise points and clusters, ADPSCAN reassigns noise points to appropriate clusters, thereby improving overall clustering quality.