

Preprint 21/2011
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.