# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 1 Introduction  
Graphs or networks represent a fundamental data structure utilized for depicting data without a fixed schema [1]. Composed of nodes and edges, nodes symbolize objects while edges denote the relationships between these objects. Clustering and classification tasks find applications across various domains. For instance, the latest methods in hyperspectral image (HSI) classification, such as M3 FuNet [2], and the CC-MIDNN [3] method for estimating arrival times, illustrate their wide-ranging impact. This paper focuses primarily on graph clustering tasks. Graph clustering is a critical task in graph data analysis, aimed at dividing vertices into distinct groups where connections within groups are dense, and those between groups are sparse. This technique is widely applied in identifying functional modules in metabolic networks [4], communities in social networks [5], research teams in collaborative networks [6], and handwritten character recognition [7, 8]. Numerous graph clustering methods have been proposed to date, encompassing a range of approaches such as graph partitioning [9], hierarchical methods [10], density-based methods [11, 12], grid-based methods [13], spectral methods [14] and propagation-based meth-ods [15]. Most existing methods successfully partition clusters. However, many methods still face challenges in practical. In particular, selecting the appropriate graph clustering technique requires careful consideration of specific application contexts anddata characteristics. For instance, the SCAN [16] is a structural graph clustering method. The core premise of the SCAN algorithm is that if two nodes are sufficiently similar in terms of their neighboring nodes, they are likely to belong to the same cluster. Unlike other clustering algorithms, SCAN can identify the unique roles of different nodes, such as identifying hub nodes that connect distinct clusters and outliers that are loosely connected to any cluster [16]. Although the SCAN algorithm has been successfully implemented in various fields, its clustering accuracy is heavily dependent on the selection of parameters \(\epsilon\) and \(\mu\). This dependency makes the clustering results extremely sensitive to parameter adjustments, and varying these parameters can lead to significant differences in clustering results [17]. Additionally, according to the SCAN algorithm's definition, any boundary nodes that are neither core nodes nor connected to core nodes are considered noise. This categorization may erroneously label many boundary nodes that have specific connectivity patterns as noise, especially in sparsely connected graphs where the lack of sufficient connections among nodes tends to increase the prevalence of noise nodes.Therefore, the main issues affecting the accuracy of structural graph clustering are:  
1. How to reduce or avoid the impact of parameter variations on clustering results? 2. How to correctly assign misclassified noise points to the appropriate clusters? Considering the limitations of existing solutions, we propose a new structural graph clustering algorithm called ADPSCAN, which includes adaptive density peak selection and noise re-clustering parts. This algorithm executes structural graph clustering in three main steps. Firstly, we use our defined methods for local density and dependency similarity to construct a decision graph based on the input data. Secondly, to adaptively identify density peaks in the decision graph, we propose using the Generalized Extreme Value (GEV) distribution to fit the local density and dependency similarity. This fitting process yields thresholds for local density and dependency similarity, which are then used to identify density peak points. These points serve as potential cluster centers and form clusters with their first-order neighbors. If two density peak points are first-order neighbors, they are merged into the same cluster.