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

By Frank Bauer, Jürgen Jost, Shiping Liu. 2011

146 citations recorded by the source corpus.

We prove the following estimate for the spectrum of the normalized Laplace operator $\Delta$ on a finite graph $G$, \begin{equation*}1- (1- k[t])^{\frac{1}{t}}\leq \lambda_1 \leq \cdots \leq \lambda_{N-1}\leq 1+ (1- k[t])^{\frac{1}{t}}, \,\forall \,\,\text{integers}\,\, t\geq 1. \end{equation*} Here $k[t]$ is a lower bound for the Ollivier-Ricci curvature on the neighborhood graph $G[t]$, which was introduced by Bauer-Jost. In particular, when $t=1$ this is Ollivier's estimates $k\leq \lambda_1\leq \ldots \leq \lambda_{N-1}\leq 2-k$. For sufficiently large $t$ we show that, unless $G$ is bipartite, our estimates for $\lambda_1$ and $\lambda_{N-1}$ are always nontrivial and improve Ollivier's estimates for all graphs with $k\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.

Subfields: Applied Mathematics, Astronomy and Astrophysics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/0ddd979cfd3a62e7934301c0ae396537977811b5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Astronomy and Astrophysics

In Geometry and Topology

Citations in the corpus

Ricci Curvature of Finite Markov Chains via Convexity of the Entropy (2011, background): “In the setting of graphs Ollivier’s Ricci curvature has been further studied in the recent preprints [6, 22, 24].”
Li–Yau inequality on finite graphs via non-linear curvature dimension conditions (2014, background): “On graphs, it has been studied in [5, 6, 10, 13, 15, 16].”