# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 4 Method
### Redefining Noise Nodes
#### 4.2.2 Re-Clustering of Noise Nodes  
During the initial clustering process, some nodes may be erroneously labeled as noise due to various reasons. Through distance-based structural similarity, we can effectively reassess the cluster membership of these nodes. Our method first focuses on noise nodes and computes their distance-based structural similarity with each cluster's centroid nodes to evaluate their similarity. The noise nodes are then assigned to the cluster with the highest similarity to the centroid, and the clustering results are updated accordingly. The pseudo-code for our method is provided in Algorithm 2. ```
Input: Graph \(G=(V,E)\), hop Output: Dictionary \(D\) representing distance similarity
1 Initialize result as list of sets for each node for up to hop hops;
2 for\(h\) from \(0\) to hop \(-1\)do
3 foreachnode\(u\) in \(V\)do
4 if\(h=0\)then
5 // Set initial adjacency
6 result\([u][h]\leftarrow\text{set}(adj)\);
7
8 else
9 // For each neighbor
10 foreachneighbor\(n\) in \(adj\)do
11 // Update result for hop
12 result\([u][h]\leftarrow\text{result}[u][h]\cup\text{result}[n][h-1]\);
13
14 Initialize distance_similarity as empty dictionary;
15 foreachnode\(x\) in \(V\)do
16 Initialize distance_similarity\([x]\);
17 foreachnode\(y\) in \(V\)do
18 if\(x=y\)then
19 distance_similarity\([x][y]\gets 1\);
20
21 else
22 // Compute intersection and union
23 Set Intersection and Union of result\([x][\text{hop}-1]\) and result\([y][\text{hop}-1]\);
24 ifUnionemptythen
25 distance_similarity\([x][y]\gets 0\);
26
27 else
28 // Similarity is intersection over union
29 distance_similarity\([x][y]\leftarrow\frac{\text{Intersection}}{\text{Union}}\);
30
31
32 return distance_similarity;
```  
**Algorithm 2**Calculate Distance-Based Structural Similarity  
Firstly, we establish a result list, to store collections of neighbor nodes for each node in the graph by the number of hops (line 1). For each hop from \(0\) to hop-1, the algorithm iterates over all nodes in the graph. At hop \(0\), the direct neighbor set of each node is directly stored in the corresponding entry in the result list. For hops greater than \(0\), the algorithm traverses through each node's neighbors, incorporating the neighbor's previous hop neighbor set into the current node's current hop neighbor collection (lines 2-8). Then, we establish a dictionary distance_similarity, to store the similarity degree between any two nodes (line 9). For every pair of nodes, x and y, within the graph, if the nodes are identical, their similarity is set to \(1\). If different, their similarity is calculated based on the intersection and union of their neighbor sets at the maximum hop count. If the union is empty, the similarity is set to 0; otherwise, the similarity is calculated as the size of the intersection divided by the size of the union (lines 10-20). For example, as shown in Figure 5, the distance-based structural similarity between nodes \(u\) and \(v\) is calculated using their \(L\)-hop neighborhood sets. Specifically, the method for calculating structural similarity is based on the ratio of the size of the intersection of these node sets to the size of their union. In the figure, the number of nodes \(n_{1},n_{2},\ldots,n_{7}\) represents the intersection of the neighborhood sets \(N_{L}(u)\cap N_{L}(v)\), and the sum of the numbers of nodes \(S_{1},S_{2},\ldots,S_{5}\) and \(n_{1},n_{2},\ldots,n_{7}\) represents the union \(N_{L}(u)\cup N_{L}(v)\). By dividing the size of the intersection by the size of the union, the distance-based structural similarity is obtained sim(u,v). Using the method above for computing structural similarity, we calculate the average structural similarity between noise nodes and each cluster. Specifically, this involves computing the average distance-based structural similarity between a node and all nodes in a cluster. If a cluster achieves the highest average similarity score, the noise node will be reassigned to this cluster.