Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs

Jürgen Jost and Shiping Liu

Contact the author: Please use for correspondence this email.
Submission date: 04. May. 2011
Pages: 20
published in: Discrete and computational geometry, 51 (2014) 2, p. 300-322 
DOI number (of the published article): 10.1007/s00454-013-9558-1
Bibtex
MSC-Numbers: 52C45, 31C20, 05C38
Keywords and phrases: Ollivier's Ricci curvature, curvature dimension inequality, local clustering, graph Laplace operator
Download full preprint: PDF (215 kB), PS ziped (364 kB)

Abstract:
In Riemannian geometry, Ricci curvature controls how fast geodesics emanating from a common source are diverging on average, or equivalently, how fast the volume of distance balls grows as a function of the radius. Recently, such ideas have been extended to Markov processes and metric spaces. Employing a definition of generalized Ricci curvature proposed by Ollivier and applied in graph theory by Lin-Yau, we derive lower Ricci curvature bounds on graphs in terms of local clustering coefficients, that is, the relative proportion of connected neighbors among all the neighbors of a vertex. This translates the above Riemannian ideas into a combinatorial setting. We also study curvature dimension inequalities on graphs, building upon previous work of several authors.