Enhancing Graph Clustering Efficiency: A Closeness Centrality Approach to Girvan-Newman Algorithm

Abstract Graph clustering is crucial in logistics, social analysis, semantic-based search engines, and urban planning for uncovering data relationships. One of the most common graph clustering algorithms is Girvan-Newman, which relies on Edge Centrality statistics by iteratively removing edges with high betweenness centrality. However, exploring alternative centrality metrics can enhance its performance. This study presents a modified Girvan-Newman clustering algorithm that adopts a different centrality metric, namely Closeness Centrality, particularly suitable for data where the distance between nodes significantly influences their clustering, such as logistic analysis, urban planning, and network route planning. Our custom closeness-centrality-based modified Girvan-Newman algorithm aims to produce more compact and densely clustered outcomes. Experimental results demonstrate that our algorithms outperform Girvan-Newman in modularity and conductance metrics using the Hat Yai Tourism urban planning dataset. Moreover, they either outperform or closely approximate Girvan-Newman in conductance metrics across several benchmarking datasets.