# ADPSCAN: Structural Graph Clustering with Adaptive Density Peak Selection and Noise Re-Clustering
## 4 Method
### Adaptive Density Peaks Selection
#### 4.1.4. Adaptive Density Peaks Selection Algorithm Procedure  
The method for adaptively selecting density peaks is outlined in Algorithm 1. First, the upper tail of local density is fitted to the GEV distribution to obtain the parameter set gev_params_rho. Subsequently, the lower tail of dependency similarity is also fitted to the GEV distribution, yielding its distribution parameters, gev_params_delta (lines 1-2). Based on these parameter sets, we calculate the thresholds for \(\rho\) and \(\delta\). The threshold for \(\rho\) is determined by setting a high probability point to isolate extreme high values, while the threshold for \(\delta\) is identified through a low probability point to recognize extreme low values (lines 3-4). The algorithm begins by initializing an empty list, density_peaks, to store the indices of the identified density peaks (line 5). It then iterates over each node \(i\) in the decision graph (line 6), checking whether the local density \(\rho[i]\) exceeds the threshold threshold_rho and the dependency similarity \(\delta[i]\) falls below the threshold threshold_delta (line 7). If both conditions are satisfied, the node \(i\) is appended to the density_peaks list (line 8). Finally, the algorithm returns the list of identified density peaks (line 9). The functions fit_gev and find_threshold are defined to fit the GEV distribution and determine the thresholds, respectively. The fit_gev function takes the data and the tail type as inputs and fits the GEV distribution accordingly (lines 10-15). For the upper tail, it directly fits the data, whereas for the lower tail, it fits the negated data to focus on the lower extremes. The find_threshold function calculates the threshold based on the fitted parameters and the specified probability. For the upper tail, it uses the probability directly, and for the lower tail, it adjusts the probability to reflect the lower extreme values (lines 16-20).And The probability is typically set to 0.95, as it represents a confidence level that ensures the selected thresholds capture the significant extreme values while maintaining robustness against outliers.  
Figure 4: Fitting plots of GEV.  
```
Input : Local density values, \(\rho\); Dependency similarity values, \(\delta\) Output : Density Peaks
1// Fit GEV distribution
2 gev_params_rho \(\leftarrow\) fit_gev(\(\rho\),'upper')
3 gev_params_delta \(\leftarrow\) fit_gev(\(\delta\),'lower')
4// Determine threshold
5 threshold_rho \(\leftarrow\) find_threshold(gev_params_rho,'upper',rho_prob)
6 threshold_delta \(\leftarrow\) find_threshold(gev_params_delta,'lower',delta_prob)
7 density_peaks \(\leftarrow\) empty list
8 for each node \(i\) in the decision graphdo
9 if\(\rho[i]\geq\)threshold_rho and \(\delta[i]\leq\)threshold_delta then
10// Identify density peaks
11 density_peaks.append(\(i\))
12 returndensity_peaks
13 Functionfit_gev(data,tail):
14 iftail == 'upper' then
15// Fit upper tail
16 params \(\leftarrow\) generatereme.fit(data)
17 else
18// Fit lower tail
19 params \(\leftarrow\) generatereme.fit(-data)
20 returnparams
21 Functionfind_threshold(params,tail_probability):
22 iftail == 'upper' then
23// Upper tail threshold
24 returngenextreme.ppff(probability, \"params)
25 else
26// Lower tail threshold
27 return-genextreme.ppff(1-probability, \"params)
```  
**Algorithm 1**Adaptive Density Peaks Selection