Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

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