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

preprint2013arXivOpen access

Abstract

We prove the following estimate for the spectrum of the normalized Laplace operator ΔΔ on a finite graph GG, \begin{equation*}1- (1- k[t])^{\frac{1}{t}}\leq λ_1 \leq \cdots \leq λ_{N-1}\leq 1+ (1- k[t])^{\frac{1}{t}}, \,\forall \,\,\text{integers}\,\, t\geq 1. \end{equation*} Here k[t]k[t] is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph G[t]G[t], which was introduced by Bauer-Jost. In particular, when t=1t=1 this is Ollivier's estimates k≤λ1≤…≤λN−1≤2−kk\leq λ_1\leq \ldots \leq λ_{N-1}\leq 2-k. For sufficiently large tt we show that, unless GG is bipartite, our estimates for λ1λ_1 and λN−1λ_{N-1} are always nontrivial and improve Ollivier's estimates for all graphs with k≤0k\leq 0. By definition neighborhood graphs are weighted graphs which may have loops. To understand the Ollivier-Ricci curvature on neighborhood graphs, we generalize a sharp estimate of the Ricci curvature given by Jost-Liu to weighted graphs with loops and relate it to the relative local frequency of triangles and loops.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.