Graph curvature via resistance distance

DOI10.1016/J.DAM.2024.01.012arXiv2302.06021WikidataQ129296465 ScholiaQ129296465MaRDI QIDQ6204296FDOQ6204296

Authors: Karel Devriendt, Andrea Ottolini, Stefan Steinerberger 

Publication date: 27 March 2024

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

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.

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

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

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)

Cites Work

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

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)