Graph curvature via resistance distance

DOI10.1016/J.DAM.2024.01.012MaRDI QIDQ6204296zbMATH OpenWikidataFDO

Authors Karel Devriendt, Andrea Ottolini, Stefan Steinerberger

Publication date 27 March 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.06021

zbMATH Keywords

Kirchhoff indexmixing timeresistancecommute time

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Local Riemannian geometry (53B20) Global Riemannian geometry, including pinching (53C20)

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 $lambd{a}_{2}geq2K$. 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.

Recommendations

• Curvature on graphs via equilibrium measures
• Graph curvature and local discrepancy
• Ricci curvature and eigenvalue estimate on locally finite graphs
• Bakry-Émery curvature and diameter bounds on graphs
• Large scale Ricci curvature on graphs

Cites work

• scientific article; zbMATH DE number 3156874 (Why is no real title available?)
• scientific article; zbMATH DE number 2121250 (Why is no real title available?)
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• scientific article; zbMATH DE number 3894218 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• scientific article; zbMATH DE number 3061533 (Why is no real title available?)
• A Simple Proof of 1 + 1 2 2 + 1 3 2 + ⋯ = π 2 6 and Related Identities
• A note on tilings and strong isoperimetric inequality
• A survey of Ricci curvature for metric spaces and Markov chains
• An edge version of the matrix-tree theorem and the wiener index
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Average distance in graphs and eigenvalues
• Bochner's method for cell complexes and combinatorial Ricci curvature
• Combinatorial curvature for planar graphs
• Correction to my paper 'A combinatorial analogue of a theorem of Myers'
• Curvature on graphs via equilibrium measures
• Effective graph resistance
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Minimizing Kirchhoff index among graphs with a given vertex bipartiteness
• On resistance-distance and Kirchhoff index
• On the geometry of metric measure spaces. I
• On the resistance matrix of a graph
• Probability on trees and networks
• Resistance distances and the Kirchhoff index in Cayley graphs
• Ricci curvature for metric-measure spaces via optimal transport
• Ricci curvature of Markov chains on metric spaces
• Ricci curvature of graphs
• Simple Proofs for and sin
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(3)

• Graph curvature and local discrepancy
• Graphs with positive Ricci curvature
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024

This page was built for publication: Graph curvature via resistance distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6204296)