# GraphDBSCAN: Optimized DBSCAN for Noise-Resistant Community Detection in Graph Clustering
## 3 Proposed Method
### Identification of Optimal DBSCAN Parameters: bestEps and minPts  
This section uses predefined clusters to determine the adaptive parameters in DBSCAN to obtain optimal parameter values based on their statistical data. Algorithm 2 depicts the algorithm for determining the optimal values of bestEps and minPts. As seen in Algorithm 2, the K-nearest neighbor (KNN) algorithm is used to identify dense points, and then circles (pre-clusters) are drawn on these points. Therefore, distinct Pts and Eps values are obtained. The optimal bestEps and minPts values are calculated using the probability density function. ```
Input: SFM (Spatial Feature Matrix) Output: bestEps, minPts
1. For each node v in SFM:
2. KNN_v \(\leftarrow\) KNearestNeighbors(v, k = 5)
3. Dense[v] \(\leftarrow\) Count(KNN_v)
4. avgDensity \(\leftarrow\) Mean(Dense)
5. Dense \(\leftarrow\) Filter(Dense > avgDensity)
6. For each pair (v_i, v_j) in Dense:
7. r \(\leftarrow\) EuclideanDistance(v_i, v_j) / 2
8. Pts[r] \(\leftarrow\) PointsWithinRadius(v_i, r)
9. Radii[r] \(\leftarrow\) r
10. bestEps \(\leftarrow\) PDF(Radii).mode()
11. minPts \(\leftarrow\) PDF(Pts).mode()
12. Return bestEps, minPts
```  
**Algorithm 2** Identify optimum _bestEps_ and _minPts_. The K-Nearest Neighbor (KNN) algorithm in the proposed method dynamically determines the optimal DBSCAN parameters (Eps and minPts). This approach is very useful due to its ability to estimate local density and adaptability to the data structure. Prior work has demonstrated the effectiveness of KNN in graph-based clustering contexts, such as predicting phases in high-entropy alloy networks [11; 12], providing a foundation for its application in GraphDBSCAN to enhance parameter optimization and noise resilience. In Algorithm 1, the inputs are graph G and its adjacency matrix, and the output is the proximity features of each node. First, for each node z in the graph, the row from the ADJ matrix corresponding to it is placed in the vector F(z). Using N as the number of features and max-Iteration as the maximum number of times the loop iterates, the following operations are performed: for both m and z nodes, the graph calculates the shortest path, \(P_{mz}\), and updates the vector values of the z node as follows:  
\[\omega_{mz}=\frac{1}{P_{mz}},\ \ \ \Delta_{mz}=\text{F}(z)-\text{F}(m) \tag{2}\]  
\[F^{t+1}(z)=\alpha F^{t}(z)+(1-\alpha)\sum_{m\in V}\omega_{mz}\Delta_{mz} \tag{3}\]  
As seen, the feature vector F(z) for each node z is updated and placed in \(F^{t+1}(z)\). This feature vector at a time (t + 1) is computed as follows: the feature vector at a time (t) (current feature vector) multiplied by \(\alpha\) plus the distance to the feature vectors of nearby nodes multiplied by \((1-\alpha)\). Thus, nodes closer together have more similar feature vectors. The spatial feature matrix of the nodes is the input to Algorithm 2, and its outputs are the best epsilon value best_Eps and the minimum number of points minPts. In this algorithm, for each vertex of the graph V, the list of its KNN points is computed, and for each point on this list, the \(Dense[v_{j}]\) value is increased by one. The dense vector displays each point's density. Considering the average density of all points, those whose density is below the average should be removed from the Dense list. Consequently, this list will only contain points with greater density than the average. Now, we calculate the Euclidean distance between points \(v_{i}\) and \(v_{j}\) in the Dense list. Furthermore, in order to determine the Pts values derived from these points, we draw a circle with radius r in the center of two points \(v_{i}\) and \(v_{j}\). This radius is given by \(r=\frac{d_{v_{i}\varphi_{j}}}{2}\).