Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds

Pim van der Hoorn (Corresponding author), Gabor Lippner, Carlo A. Trugenberger, Dmitri Krioukov

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)

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. Here the scaling of the average degree, as a function of the graph size, can range from nearly logarithmic to nearly linear.

Original languageEnglish
Article number3
Pages (from-to)671-712
Number of pages42
JournalDiscrete and Computational Geometry
Volume70
Issue number3
DOIs
Publication statusPublished - Oct 2023

Keywords

  • Graph curvature
  • Ollivier–Ricci curvature
  • Random geometric graphs
  • Riemannian manifolds

Fingerprint

Dive into the research topics of 'Ollivier Curvature of Random Geometric Graphs Converges to Ricci Curvature of Their Riemannian Manifolds'. Together they form a unique fingerprint.

Cite this