Discrete curvature on graphs from the effective resistance

Abstract

This article introduces a new approach to discrete curvature based on the concept of effective resistances. We propose a curvature on the nodes and links of a graph and present the evidence for their interpretation as a curvature. Notably, we find a relation to a number of well-established discrete curvatures (Ollivier, Forman, combinatorial curvature) and show evidence for convergence to continuous curvature in the case of Euclidean random graphs. Being both efficient to calculate and highly amenable to theoretical analysis, these resistance curvatures have the potential to shed new light on the theory of discrete curvature and its many applications in mathematics, network science, data science and physics.

arXiv comment37 pages, 7 figures. Updates in this version: Section 3.2 added, Appendix B added, Figure 3 extended, Proof of Proposition 2 corrected

References in corpus (18)

• Analysis of a continuous-time model of structural balance
• Network Geometry
• Forman curvature for complex networks
• Comparative analysis of two discretizations of Ricci curvature for complex networks
• A Universal Construction for (Co)Relations
• Combinatorial Quantum Gravity: Geometry from Random Bits
• Unfolding the multiscale structure of networks with dynamical Ollivier-Ricci curvature
• Ollivier-Ricci curvature convergence in random geometric graphs
• Some Relativistic and Gravitational Properties of the Wolfram Model
• Effective resistance is more than distance: Laplacians, Simplices and the Schur complement
• Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving
• Enhanced Forman curvature and its relation to Ollivier curvature
• Heuristic and computer calculations for the magnitude of metric spaces
• Heterogeneous manifolds for curvature-aware graph embedding
• Curvature-based Methods for Brain Network Analysis
• Electric currents in infinite networks
• Characterizations of Forman curvature
• Ollivier Ricci-flow on weighted graphs

Cited by in corpus (9)

• Augmentations of Forman's Ricci Curvature and their Applications in Community Detection
• Quantum entropy couples matter with geometry
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Graphs with nonnegative resistance curvature
• A Cosine Rule-Based Discrete Sectional Curvature for Graphs
• Exploring the space of graphs with fixed discrete curvatures
• On Steinerberger Curvature and Graph Distance Matrices
• Characterizing Physician Referral Networks with Ricci Curvature
• Curvature of an Arbitrary Surface for Discrete Gravity and for $d=2$ Pure Simplicial Complexes