From Dense Graphs to Meaningful Communities: Assessing Community Quality Using Geodesic Distance Modularity on Metric Backbone-Sparsified Networks
- Conference: The 12th International Conference on Social Networks Analysis, Management and Security (IEEE SNAMS2025)
- DOI: https://doi.org/10.1109/SNAMS67467.2025.11391193
- Presentation Slides: Click to view on ResearchGate
Abstract:
Community detection serves as a key component of network science, essential for revealing and examining structures within complex networks. This study offers a thorough examination that combines theoretical concepts with detailed practical evaluation. At the heart of our investigation are two interrelated methodologies: the Geodesic Distance Metric (GDM), which serves as a structure-aware, label-independent evaluation tool; and the Metric Backbone, a parameter-free sparsification approach that maintains essential community structures. We present and assess a scalable pipeline for community detection that utilizes Metric Backbone sparsification in conjunction with community detection algorithms, with outcomes evaluated through various well-known quality metrics. Our systematic empirical evaluation across seven diverse real-world datasets shows that Metric Backbone sparsification leads to significant edge reduction-ranging from 14% in sparse citation networks to 71% in dense social networks-while preserving community detection quality. Interestingly, the High School dataset maintains F1 and NMI scores of 0.970 even with a 71% reduction in edges, whereas the Amazon co-purchase network demonstrates consistent performance with a 29% sparsification. The results emphasize that Metric Backbone sparsification improves computational efficiency and facilitates the use of geodesic-based metrics such as GDM in identifying compact, well-separated communities. This thorough analysis presents the initial systematic review of geodesic-based community evaluation on structurepreserving sparsified networks, delivering valuable insights into the conditions under which parameter-free sparsification preserves rather than obstructs community detection across various network types.