# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 3 Problem Definition  
In this paper, we focus on an unweighted undirected graph \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges, with \(|V|\) represented by \(n\) and \(|E|\) by \(m\). The objective of this paper is to develop a new structural graph clustering algorithm that adaptively selects density peaks as potential cluster centers, thereby reducing dependency on parameters and improving clustering accuracy by reassigning noise points. The key parameters involved in the algorithm are summarized in Table 1.  
**Definition 1** (Structural Neighbors). : _For a graph \(G(V,E)\), the structural neighbors of a vertex \(u\) include its neighboring vertices and itself, denoted as \(N[u]=\{v\in V\mid(u,v)\in E\}\cup\{u\}\)._  
Note that, the degree of \(u\), denoted by \(\deg[u]\), is the cardinality of \(N[u]\) (i.e., \(\deg[u]=|N[u]|\)). The open neighborhood of \(u\), denoted by \(N(u)\), is the set of neighbors of \(u\) (i.e., \(N(u)=\{v\in V\mid(u,v)\in E\}\)). **Definition 2** (Structural Similarity). : _The structural similarity between two vertices \(u\) and \(v\) in a graph is defined as the number of common neighbors between \(u\) and \(v\) divided by the square root of the product of the degrees of \(u\) and \(v\). This metric is formulated as shown in Equation (1) and denoted by \(\sigma(u,v)\)._  
\[\sigma(u,v)=\frac{|N[u]\cap N[v]|}{\sqrt{deg[u]\cdot deg[v]}} \tag{1}\]  
In the algorithm design section, two metrics are defined for each vertex: local density and dependency similarity. Utilizing these definitions, density peak vertices can be identified, and the algorithm's extension steps can then be used to form the final set of clusters. **Definition 3** (Local Density). : _Given \(\mu_{uv}=\frac{\sigma_{v}}{\sigma(u,v)}\), where vertex \(v\) is a structural neighbor of vertex \(u\), the local density of vertex \(u\) is defined as the sum of the values of \(\sigma(u,v)\) under a standard normal distribution for \(\mu_{uv}\), as shown in Equation (2) and denoted by \(\rho_{u}\)._  
\[\rho_{u}=\sum_{v\in N[u]}\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\mu_{uv}^{2}}{ 2}\right) \tag{2}\]  
**Definition 4** (Dependency Similarity). : _The maximum structural similarity between vertex \(u\) and any of its neighboring vertices that have a higher local density than \(u\) is referred to as dependency similarity. This measure is presented in Equation (3) and denoted by \(\delta_{u}\)._  
\[\delta_{u}=\max_{v:\rho_{v}>\rho_{u},v\in N(u)}\left(\sigma(u,v)\right) \tag{3}\]  
For example, in Figure 0(a), the first-order neighbors of node \(u\) are \(v_{1}\), \(v_{2}\), and \(v_{3}\). Among these, \(v_{1}\) and \(v_{3}\) have higher local densities than node \(u\). The dependency similarity \(\delta_{u}\) is the maximum structural similarity between \(u\) and either \(v_{1}\) or \(v_{3}\). Based on local density and dependency similarity, a definition for density peak vertices can be established. A vertex \(u\) is designated as a density peak vertex if it possesses a relatively high local density \(\rho_{u}\) and a relatively low dependency similarity \(\delta_{u}\).