TY - JOUR
T1 - Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds
AU - van der Hoorn, Pim
AU - Lippner, Gabor
AU - Trugenberger, Carlo A.
AU - Krioukov, Dmitri
PY - 2023/10
Y1 - 2023/10
N2 - 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. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.
AB - 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. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.
KW - Graph curvature
KW - Ollivier–Ricci curvature
KW - Random geometric graphs
KW - Riemannian manifolds
UR - http://www.scopus.com/inward/record.url?scp=85162982314&partnerID=8YFLogxK
U2 - 10.1007/s00454-023-00507-y
DO - 10.1007/s00454-023-00507-y
M3 - Article
AN - SCOPUS:85162982314
SN - 0179-5376
VL - 70
SP - 671
EP - 712
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 3
M1 - 3
ER -