Graph curvature via resistance distance

Journal article

Let G=(V,E) be a finite, combinatorial graph. We define a notion of curvature on the vertex set 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 λ2≥2K. We obtain matching two-sided bounds on the maximal commute time between any two vertices in terms of |E|⋅|V|−1⋅K−1. Moreover, we derive quantitative rates for the mixing time of the corresponding Markov chain and prove a general equilibrium result.

Authors: Devriendt, K; Ottolini, A; Steinerberger, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Discrete Applied Mathematics
• Volume: 348
• Pages: 68-78
• Publication date: 2024-01-26
• Acceptance date: 2024-01-10
• DOI: 10.1016/j.dam.2024.01.012
• EISSN: 1872-6771
• ISSN: 0166-218X
• Language: English
• Keywords: commute time; Kirchhoff index; mixing time; graph; curvature; resistance