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 (28)

• Fast unfolding of communities in large networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Finding community structure in very large 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
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Origins of fractality in the growth of complex networks
• 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
• Network Geometry
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Chimera states in brain networks: empirical neural vs. modular fractal connectivity
• Spectral coarse-graining of complex networks
• Multiscale unfolding of real networks by geometric renormalization
• Chimera states in complex networks: interplay of fractal topology and delay
• Emergence of slow-switching assemblies in structured neuronal networks
• Diffusion geometry unravels the emergence of functional clusters in collective phenomena
• Ollivier-Ricci curvature convergence in random geometric graphs
• Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Scale-dependent measure of network centrality from diffusion dynamics
• Coarse Ricci curvature for continuous-time Markov processes
• THe largest eigenvalue of sparse random graphs

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