Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature

Abstract

Describing networks geometrically through low-dimensional latent metric spaces has helped design efficient learning algorithms, unveil network symmetries and study dynamical network processes. However, latent space embeddings are limited to specific classes of networks because incompatible metric spaces generally result in information loss. Here, we study arbitrary networks geometrically by defining a dynamic edge curvature measuring the similarity between pairs of dynamical network processes seeded at nearby nodes. We show that the evolution of the curvature distribution exhibits gaps at characteristic timescales indicating bottleneck-edges that limit information spreading. Importantly, curvature gaps are robust to large fluctuations in node degrees, encoding communities until the phase transition of detectability, where spectral and node-clustering methods fail. Using this insight, we derive geometric modularity to find multiscale communities based on deviations from constant network curvature in generative and real-world networks, significantly outperforming most previous methods. Our work suggests using network geometry for studying and controlling the structure of and information spreading on networks.

References in corpus (13)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Statistical Mechanics of Community Detection
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Analysis of the structure of complex networks at different resolution levels
• Self-similarity of complex networks and hidden metric spaces
• Graph spectra and the detectability of community structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Spectral coarse-graining of complex networks
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Coarse Ricci curvature for continuous-time Markov processes

Cited by in corpus (8)

• Discrete curvature on graphs from the effective resistance
• Interpretable statistical representations of neural population dynamics and geometry
• Augmentations of Forman's Ricci Curvature and their Applications in Community Detection
• PyGenStability: Multiscale community detection with generalized Markov Stability
• Quantum entropy couples matter with geometry
• Emergent time, cosmological constant and boundary dimension at infinity in combinatorial quantum gravity
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Exploring the space of graphs with fixed discrete curvatures