# GraphDBSCAN: Optimized DBSCAN for Noise-Resistant Community Detection in Graph Clustering
## 3 Proposed Method
### Improved Newman-Girvan Algorithm  
Our method's improved Newman-Girvan (NG) algorithm is based on two factors: \"edge betweenness\" and \"node closeness\". In the improved NG algorithm, these two factors are used to select the edges to be removed. The traditional NG algorithm for point clustering sorts edges according to edge betweenness and discards the edge with the highest betweenness value. When two edges have the same highest betweenness values, it deletes one of them at random. This could have a negative impact on the clustering process. To circumvent this issue, the improved NG, when multiple edges with the same highest betweenness are identified, the sum of the closeness centrality values of the two nodes forming each edge is calculated, and the edge is removed if the sum of the closeness centrality value is the smallest. It is evident that the higher the closeness value of a node, the more central it is, or, in other words, the node is located in the central area. The more a node is located in the non-central area, the lower its closeness value, and the edge connecting the two non-central nodes must be removed first. Thus, the improved NG in Algorithm 3 provides a superior method for identifying communities. Algorithm 4 demonstrates the proposed method's procedure. ```
Input: G (Graph), targetCommunities Output: Communities
1. G_copy \(\leftarrow\) G
2. Communities \(\leftarrow\) ConnectedComponents(G_copy)
3. bestCommunities \(\leftarrow\) Communities
4. bestMod \(\leftarrow\) Modularity(G, Communities)
5. While G_copy.Edges > 0 and | Communities | \(<\) targetCommunities * 1.5:
6. Bet \(\leftarrow\) EdgeBetweenness(G_copy)
7. maxBets \(\leftarrow\) EdgesWithMax(Bet)
8. If |maxBets| > 1:
9. Close \(\leftarrow\) ClosenessCentrality(G_copy)
10. edgeToRemove \(\leftarrow\) min(maxBets, key = lambda e: Close[e[0]] + Close[e[1]])
11. Else:
12. edgeToRemove \(\leftarrow\) maxBets[0]
13. G_copy.RemoveEdge(edgeToRemove)
14. Communities \(\leftarrow\) ConnectedComponents(G_copy)
15. mod \(\leftarrow\) Modularity(G, Communities)
16. If | Communities-targetCommunities| | \(<\) | bestCommunities-targetCommunities| and mod > 0:
17. bestCommunities \(\leftarrow\) Communities
18. bestMod \(\leftarrow\) mod
19. If | Communities| \(\geq\) targetCommunities and mod > bestMod-0.05:
20. Break
21. Return bestCommunities
```  
**Algorithm 3** Improved NG algorithm. Graph G is the input of Algorithm 3, and the identified communities are the output. This algorithm presents the improved NG algorithm. For each edge \(\left(v_{i},v_{j}\right)\) in the graph, the betweenness value of the edge \(\left(v_{i},v_{j}\right)\) is calculated and placed in the Bet vector. The vector's edges with the highest value are selected and placed in \(maxBets\). If more than one edge is found in maxBets, for each edge \(\left(v_{i},v_{j}\right)\) in \(maxBets\), the sum of the closeness values of the two nodes \(v_{i}\) and \(v_{j}\) is calculated and added to the Close list. Then, the edge with the lowest value in this list is selected and removed. This way, rather than arbitrarily removing an edge from the Close list, the deletion of edges is performed more effectively. The purpose of this method for selecting edges is to prioritize the removal of edges connected to marginal points (lower closeness). This improves the effectiveness of edge removal and community detection. If \(maxBets\) contains only one edge, that edge is removed. Following this, the calculation of \(Bet\left(v_{i},v_{j}\right)\) is repeated for the edges affected by the removal. This operation continues until there are no more edges. The proposed method in this paper, by combining optimized DBSCAN and improved Newman-Girvan clustering, takes an important step towards solving the challenges of community detection in social networks. The main contributions of this method include automatic optimization of DBSCAN parameters, proximity-based feature extraction, and improved Newman-Girvan clustering.