Comparative analysis of two discretizations of Ricci curvature for complex networks

Abstract

We have performed an empirical comparison of two distinct notions of discrete Ricci curvature for graphs or networks, namely, the Forman-Ricci curvature and Ollivier-Ricci curvature. Importantly, these two discretizations of the Ricci curvature were developed based on different properties of the classical smooth notion, and thus, the two notions shed light on different aspects of network structure and behavior. Nevertheless, our extensive computational analysis in a wide range of both model and real-world networks shows that the two discretizations of Ricci curvature are highly correlated in many networks. Moreover, we show that if one considers the augmented Forman-Ricci curvature which also accounts for the two-dimensional simplicial complexes arising in graphs, the observed correlation between the two discretizations is even higher, especially, in real networks. Besides the potential theoretical implications of these observations, the close relationship between the two discretizations has practical implications whereby Forman-Ricci curvature can be employed in place of Ollivier-Ricci curvature for faster computation in larger real-world networks whenever coarse analysis suffices.

Published version. New results added in this version. Supplementary tables can be freely downloaded from the publisher website

References in corpus (8)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Hyperbolic Geometry of Complex Networks
• Community Structure in Jazz
• Robust network community detection using balanced propagation
• Emergent Hyperbolic Network Geometry
• Emergent Complex Network Geometry
• Systematic evaluation of a new combinatorial curvature for complex networks

Cited by in corpus (19)

• Network Geometry
• Discrete Ricci curvatures for directed networks
• Ollivier-Ricci curvature convergence in random geometric graphs
• Discrete curvature on graphs from the effective resistance
• Self-Assembly of Geometric Space from Random Graphs
• Persistent homology of unweighted complex networks via discrete Morse theory
• Edge-based analysis of networks: Curvatures of graphs and hypergraphs
• Teleconnection patterns of different El Niño types revealed by climate network curvature
• Degree difference: A simple measure to characterize structural heterogeneity in complex networks
• Network-centric indicators for fragility in global financial indices
• Augmentations of Forman's Ricci Curvature and their Applications in Community Detection
• Quantum entropy couples matter with geometry
• Physics in non-fixed spatial dimensions via random networks
• Forman-Ricci curvature and Persistent homology of unweighted complex networks
• Community Detection in networks by Dynamical Optimal Transport Formulation
• Finding Influential Cores via Normalized Ricci Flows in Directed and Undirected Hypergraphs with Applications
• A Cosine Rule-Based Discrete Sectional Curvature for Graphs
• Application of discrete Ricci curvature in pruning randomly wired neural networks: A case study with chest x-ray classification of COVID-19
• Exploring the space of graphs with fixed discrete curvatures