Graph curvature via resistance distance

Abstract

Let $G=(V,E)$ be a finite, combinatorial graph. We define a notion of curvature on the vertices $V$ via the inverse of the resistance distance matrix. We prove that this notion of curvature has a number of desirable properties. Graphs with curvature bounded from below by $K>0$ have diameter bounded from above. The Laplacian $L=D-A$ satisfies a Lichnerowicz estimate, there is a spectral gap ${\lambda }_2\ge 2K$. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of $|E|\cdot |V{|}^{-1}\cdot K^{-1}$. Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result.

15 pages, 2 figures