Curvature based method speeds up graph sparsification while keeping communities intact
Curvature-Guided Sparsification for Graphs with Community Structure
Social and Information Networks
Summary
Large networks often have hidden groups called communities. It’s tricky to shrink these networks without messing up these groups. The authors found a way to quickly remove some connections using a simpler math trick before applying a more detailed method, keeping the groups mostly the same. This approach keeps the important structure but runs faster than older methods. Tests showed it works well on both made-up and real networks.
What this means in practice
- •For network engineers: Reduce large communication networks while preserving key community connections to improve monitoring and analysis efficiency.
- •For social media platform developers: Create smaller network representations that maintain user community structure to speed up recommendation algorithms without loss of accuracy.
Authors
Avin Kolahdooz, Jose Jairo Garcia, Sarah Percival
Abstract
Graph sparsification in large-scale networks often requires balancing structural accuracy and computational efficiency. Curvature-based methods, particularly Ollivier-Ricci curvature (ORC), have shown strong performance in identifying inter-community bridges, but their computational cost limits scalability. In this work, we propose a two-stage curvature-guided pipeline for graph sparsification with the goal of preserving community structure. We first use the Lower Ricci Curvature, a combinatorial lower bound of the ORC, to perform efficient edge filtering, substantially reducing graph size before applying the computationally intensive optimal-transport-based ORC curvature and Ricci flow. Results from empirical studies on synthetic and real-world datasets demonstrate that the combined LRC-ORC pipeline can achieve community-recovery accuracy comparable to ORC-only sparsification in terms of Adjusted Rand Index (ARI) and Normalized Mutual Information (NMI), while reducing runtime on most evaluated benchmarks. Our findings suggest that integrating combinatorial and geometric curvature notions provides a computationally efficient and structurally principled framework for graph sparsification in complex networks.