Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds

Abstract

Curvature is a fundamental geometric characteristic of smooth spaces. In recent years different notions of curvature have been developed for combinatorial discrete objects such as graphs. However, the connections between such discrete notions of curvature and their smooth counterparts remain lurking and moot. In particular, it is not rigorously known if any notion of graph curvature converges to any traditional notion of curvature of smooth space. Here we prove that in proper settings the Ollivier-Ricci curvature of random geometric graphs in Riemannian manifolds converges to the Ricci curvature of the manifold. This is the first rigorous result linking curvature of random graphs to curvature of smooth spaces. Our results hold for different notions of graph distances, including the rescaled shortest path distance, and for different graph densities. With the scaling of the average degree, as a function of the graph size, ranging from nearly logarithmic to nearly linear.

References in corpus (2)

• Hyperbolic Geometry of Complex Networks
• Ollivier-Ricci curvature convergence in random geometric graphs

Cited by in corpus (7)

• Ollivier-Ricci curvature convergence in random geometric graphs
• Convergence of Combinatorial Gravity
• The birth of geometry in exponential random graphs
• Recovering General Relativity from a Planck scale discrete theory of quantum gravity
• Coarse extrinsic curvature of Riemannian submanifolds
• Computing distances on Riemann surfaces
• Curvature of an Arbitrary Surface for Discrete Gravity and for $d=2$ Pure Simplicial Complexes