# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 2 Related Work  
In this section, we review the Density Peaks Clustering (DPC) algorithm and structural graph clustering techniques.  
**Density Peaks Clustering.** The DPC algorithm [18] is a density-based clustering technique primarily employed to identify cluster centers through local density and distance metrics. One of the primary advantages of this method is its inherent ability to identify distinct clusters naturally, without the necessity of predefining the number of clusters. The essence of the DPC method lies in pinpointing data points that have the highest local density and are significantly distant from other high-density points, designating them as cluster centers. While the DPC algorithm demonstrates robust clustering capabilities, its performance can be compromised when dealing with non-uniform datasets. Recently, several variants of the DPC have been proposed to enhance the original algorithm. CPF [19] improves clustering by partitioning data into areas of distinct densities before identifying density peaks within each area, thus grouping points within the same cluster. The BC-DPC algorithm [20] refines cluster center identification by creating balanced densities to mitigate differences among clusters. However, due to fundamental differences in problem definitions, these methods do not apply to structural graph clustering.  
**Structural Graph Clustering.** The SCAN algorithm [16] is a well-known method within the field of graph clustering. Its core concept is based on a simple yet powerful principle: if two nodes are sufficiently similar within their neighborhood, then they are likely to belong to the same cluster. This method not only identifies clustering results but also recognizes the unique roles of different nodes within the graph. For instance, the algorithm can identify hub nodes that connect different clusters and outliers that do not have strong connections to any cluster. This capability allows for a deeper understanding of the intrinsic structure and relationships within the graph.  
Despite its effectiveness, the SCAN algorithm [16] exhibits lower efficiency when handling large-scale graphs, leading to the development of various optimized versions. One line of research has focused on overcoming the efficiency challenges of the original SCAN algorithm in processing large graphs. For instance, the SCAN++ algorithm [1] reduces redundant similarity calculations significantly by accurately identifying vertex types and their two-hop neighbors. Additionally, the pSCAN algorithm [11], a state-of-the-art method based on pruning techniques, optimizes the computation sequence of vertices and implements timely pruning strategies to accelerate clustering. This approach avoids unnecessary similarity calculations after vertex types have been determined, thereby enhancing processing efficiency.  
On another front, methods like GS*-Query [17], developed based on the GS*-Index [17] algorithm, offer an efficient response to clustering queries. SCAN-XP [21], ppSCAN [22], and GBBSIndexSCAN [23] leverage parallel computing technologies to expedite the generation of clustering results, making them particularly suitable for the rapid processing of large-scale network data.  
Although all these methods have made advancements in the field of graph clustering, they often fail to adequately address issues related to parameter dependency or clustering accuracy. This paper proposes a structural graph clustering algorithm based on the adaptive selection of density peaks, which effectively eliminates reliance on input parameters. Additionally, we propose a distance-based structural similarity method for accurately managing noise nodes, thereby enhancing the quality of the clustering process, as well as its level of automation.