Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
21/2011

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

Jürgen Jost and Shiping Liu

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.

Received:
May 4, 2011
Published:
May 5, 2011
MSC Codes:
52C45, 31C20, 05C38
Keywords:
Ollivier's Ricci curvature, curvature dimension inequality, local clustering, graph Laplace operator

Related publications

inJournal
2014 Repository Open Access
Jürgen Jost and Shiping Liu

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

In: Discrete and computational geometry, 51 (2014) 2, pp. 300-322