Preprint 26/2015

Generalized Ricci curvature and the geometry of graphs

Frank Bauer, Bobo Hua, Jürgen Jost, and Shiping Liu

Contact the author: Please use for correspondence this email.
Submission date: 13. Apr. 2015
Pages: 16
published in: Actes des rencontres du CIRM, 3 (2013) 1, p. 69-78 
DOI number (of the published article): 10.5802/acirm.56
Bibtex
Download full preprint: PDF (303 kB)

Abstract:
In this contribution, we shall explain how the generalized Ricci curvature as defined by Ollivier relates to other characteristic properties of graphs, like the clustering coefficient that is important for the analysis of social and other networks. We also show how this generalized Ricci curvature controls the smallest as well as the largest eigenvalue of the normalized graph Laplacian. In fact, we obtain nontrivial eigenvalue estimates for all graphs that are not bipartite. Our constructions utilize the concept of the neighborhood graph, a geometric representation of the concept of a random walk on a graph. Thereby, we see a natural link between Ricci curvature, eigenvalues, and stochastic analysis. While these principles hold in more generality, here we only explore them for graphs.

30.11.2017, 01:42