Ollivier-Ricci curvature convergence in random geometric graphs
Open Access
- 5 March 2021
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Research
- Vol. 3 (1), 013211
- https://doi.org/10.1103/PhysRevResearch.3.013211
Abstract
Connections between continuous and discrete worlds tend to be elusive. One example is curvature. Even though there exist numerous nonequivalent definitions of graph curvature, none is known to converge in any limit to any traditional definition of curvature of a Riemannian manifold. Here we show that Ollivier curvature of random geometric graphs in any Riemannian manifold converges in the continuum limit to Ricci curvature of the underlying manifold, but only if the definition of Ollivier graph curvature is properly generalized to apply to mesoscopic graph neighborhoods. This result establishes a rigorous link between a definition of curvature applicable to networks and a traditional definition of curvature of smooth spaces.Funding Information
- Army Research Office (W911NF-16-1-0391, W911NF-17-1-0491)
- National Science Foundation (IIS-1741355, DMS-1800738)
- Government of Canada
- Northeastern University
- Province of Ontario
This publication has 74 references indexed in Scilit:
- Cool horizons for entangled black holesFortschritte der Physik, 2013
- Curvature, Geometry and Spectral Properties of Planar GraphsDiscrete & Computational Geometry, 2011
- Random Geometric ComplexesDiscrete & Computational Geometry, 2011
- Combinatorial curvature for planar graphsJournal of Graph Theory, 2001
- Matching theorems and empirical discrepancy computations using majorizing measuresJournal of the American Mathematical Society, 1994
- Matching Random Samples in Many DimensionsThe Annals of Applied Probability, 1992
- Minimax Grid Matching and Empirical MeasuresThe Annals of Probability, 1991
- Space-time as a causal setPhysical Review Letters, 1987
- On the curvature of piecewise flat spacesCommunications in Mathematical Physics, 1984
- A note on two problems in connexion with graphsNumerische Mathematik, 1959