Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator

Frank Bauer, Jürgen Jost, and Shiping Liu

Contact the author: Please use for correspondence this email.
Submission date: 19. May. 2011
Pages: 24
published in: Mathematical research letters, 19 (2012) 6, p. 1185-1205 
DOI number (of the published article): 10.4310/MRL.2012.v19.n6.a2
Bibtex
MSC-Numbers: 60J05, 51F99, 05C50
Keywords and phrases: Ollivier-Ricci curvature, normalized graph Laplace operator, largest eigenvalue, random walk, neighborhood graph
Download full preprint: PDF (326 kB)

Abstract:

We prove the following estimate for the spectrum of the normalized Laplace operator Δ on a finite graph G,

Here k[t] is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph G[t] (here we use the convention G[1] = G), which was introduced by Bauer-Jost. In particular, when t = 1 this is Ollivier’s estimate k ≤ λ₁ and a new sharp upper bound λ_N-1 ≤ 2 -k for the largest eigenvalue. Furthermore, we prove that for any G when t is sufficiently large, 1 > (1 -k[t]) which shows that our estimates for λ₁ and λ_N-1 are always nontrivial and the lower estimate for λ₁ improves Ollivier’s estimate k ≤ λ₁ for all graphs with k ≤ 0. By definition neighborhood graphs possess many loops. To understand the Ollivier-Ricci curvature on neighborhood graphs, we generalize a sharp estimate of the curvature given by Jost-Liu to graphs which may have loops and relate it to the relative local frequency of triangles and loops.