Source-linked AI summary
Comparative analysis of two discretizations of Ricci curvature for complex networks
Areejit Samal, R. P. Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, Jürgen Jost
TL;DR
The paper addresses whether two theoretically distinct discretizations of Ricci curvature provide related information about complex networks. It empirically compares Ollivier-Ricci and Forman-Ricci curvature across model and real-world networks, finding strong correlation in many cases and an even stronger relationship for augmented Forman-Ricci curvature. The findings support using Forman-Ricci curvature for faster coarse analysis of large networks while preserving the distinction between the notions.
Problem
The two discretizations arise from different theoretical considerations and capture different geometric properties, leaving their empirical relationship across complex networks to be assessed.
Method
The study performs an empirical comparison of Ollivier-Ricci, Forman-Ricci, and augmented Forman-Ricci curvature across model and real-world networks.
Results
The two discretizations are highly correlated in many networks, with still higher correlation for augmented Forman-Ricci curvature, especially in real networks.
Takeaways & Limitations
Forman-Ricci curvature can support faster analysis of larger networks when coarse analysis suffices, while the two discretizations should not be treated as interchangeable because they capture different aspects of network behavior.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
The paper compares two graph-based discretizations of Ricci curvature that arise from different geometric principles and capture different network properties. Despite these differences, the study finds strong correlation between them across many model and real-world networks, with practical computational implications.
- Study scope: The study empirically compares Forman-Ricci and Ollivier-Ricci curvature in model and real-world complex networks.It also evaluates augmented Forman-Ricci curvature, which accounts for two-dimensional simplicial complexes arising in graphs.
- Main finding: The two discretizations are highly correlated in many networks, especially when using augmented Forman-Ricci curvature.The reported correlation is particularly strong for real networks.
- Motivation: Ricci curvature provides geometric tools for analyzing network structure, dynamics, and evolution by assigning local geometric information to network edges.Both discretizations are edge-based measures that encode local properties around each edge.
- Distinct discretizations: Ollivier-Ricci curvature is associated with clustering and network coherence, whereas Forman-Ricci curvature captures dispersal and topology.The two notions were developed from different properties of classical Ricci curvature and therefore emphasize different network behaviors.
- Practical implication: Forman-Ricci curvature is substantially simpler and faster to compute, making it useful for large-network analysis when coarse information is sufficient.The paper cautions that correlation does not make Forman-Ricci curvature a general substitute or proxy because the discretizations capture different aspects of network behavior.
B. Ollivier-Ricci curvature
Ollivier-Ricci curvature compares the distance between neighboring probability measures with the distance between their centers. In networks, this comparison is implemented through Wasserstein transportation and reflects local motifs and random-walk structure.
- Definition: Ollivier-Ricci curvature compares the distance between the centers of two balls with the transportation distance between their measures.Positive curvature corresponds to balls being closer than their centers, while negative curvature corresponds to balls being farther apart.
- Network formulation: For graph networks, the ball measures around vertices are discrete probability measures, and their Wasserstein distance is computed through admissible transport plans.These plans describe how mass is moved from the measure around one vertex to the measure around another.
- Transportation: The Wasserstein distance is the minimum cost of transporting one ball measure into the other along graph paths.For unweighted networks, the combinatorial graph metric is the natural practical choice for transportation distances.
- Network structure: In networks, Wasserstein distance depends on the triangles, quadrangles, and pentagons containing the two vertices.It can also be computed using either lazy or non-lazy random walks; this study uses the lazy option in its implementation.
- Vertex extension: Ollivier-Ricci curvature is fundamentally edge-based, while vertex curvature can be defined by summing the curvatures of incident edges.This vertex construction is analogous to scalar curvature in Riemannian geometry.
C. Forman-Ricci curvature
Forman-Ricci curvature discretizes Ricci curvature through weighted CW complexes, including weighted graphs, rather than through Markov chains and metric-measure spaces. In the graph setting, its edge formula uses local edge and vertex weights and has a simple combinatorial interpretation.
- Framework: Forman-Ricci curvature is defined in weighted CW cell complexes, including polygonal meshes and weighted graphs.This framework differs conceptually from Ollivier-Ricci curvature, which is formulated using Markov chains and metric-measure spaces.
- Construction: Forman’s graph curvature is derived from a discrete Bochner-Weitzenböck formula for an edge connecting vertices v1 and v2.Edges serve as discrete counterparts of tangent directions in the smooth setting.
- Weighted formulation: The weighted edge formula depends on the weight of the edge, the weights of its endpoint vertices, and the other edges incident to those endpoints.The incident-edge sets exclude the edge whose curvature is being evaluated.
- Combinatorial case: When all edge and vertex weights equal 1, the Forman-Ricci formula reduces to a simple combinatorial expression for graph edges.In this case, the curvature captures flow through an edge and the dispersal of geodesics.
- Vertex extension: Forman-Ricci curvature is edge-based, and vertex curvature can be obtained by summing the curvatures of incident edges.This mirrors the analogous vertex construction for Ollivier-Ricci curvature.
Augmented Forman-Ricci curvature
The augmented Forman-Ricci framework extends graph curvature to two-dimensional polyhedral complexes and incorporates weights of simplices, edges, and vertices. In this work, the augmented curvature accounts specifically for triangular simplices while excluding longer cycles.
- Graphs can be extended into two-dimensional polyhedral complexes by inserting simplices into connected vertex triples and longer cycles.This construction represents higher-order correlations between vertices.
- Forman’s curvature formula for these complexes includes weights assigned to simplices, edges, and vertices.
- The augmented Forman-Ricci curvature incorporates triangular simplices, or cycles of length 3, while neglecting cycles of length 4 and greater.
- In unweighted networks, the augmented curvature uses unit weights for faces, edges, and vertices and is explored alongside ordinary Forman-Ricci curvature.
D. Ollivier’s vs. Forman’s Ricci curvature: A first comparison
Simple graph examples show that Ollivier-Ricci and Forman-Ricci curvature can agree or diverge because they encode different geometric properties. Nevertheless, numerical results indicate high correlation between them in many complex networks, strengthened by augmenting Forman curvature with triangles.
- In complete graphs, overlapping neighborhoods produce Ollivier-Ricci curvature near 1 for large n, while Forman-Ricci curvature follows vertex degree.
- In double-star graphs, distant neighborhood vertices yield quite negative Ollivier-Ricci curvature, while Forman-Ricci curvature equals 2 − m − m′.
- The numerical analysis finds that Ollivier-Ricci and Forman-Ricci curvature are highly correlated in many complex networks despite contrasting behavior in simple examples.
- Augmented Forman-Ricci curvature is better correlated with Ollivier-Ricci curvature because triangles no longer contribute negatively to the Forman measure.
III. BENCHMARK DATASET OF COMPLEX NETWORKS
The benchmark comprises four undirected network models and seventeen real-world networks, sampled across varied sizes and average degrees. Curvature calculations use unweighted graphs and, for Ollivier-Ricci curvature, the largest connected component.
- The model benchmark includes Erdős-Rényi, Watts-Strogatz, Barabási-Albert, and Hyperbolic Graph Generator networks.
- Model networks were generated with varied sizes and average degrees, including 100 random-seed samples for each parameter combination.
- The real-world benchmark contains seventeen widely studied undirected networks spanning communication, infrastructure, biological, and interaction systems.
- All benchmark networks are unweighted, while Ollivier-Ricci edge curvature is computed on each network’s largest connected component.
A. Comparison between Forman-Ricci and Ollivier-Ricci curvature in model and real networks
Across model and real-world networks, Ollivier-Ricci curvature is often positively correlated with Forman-Ricci curvature, with stronger agreement generally observed for the augmented version and at the vertex level. However, correlations vary by network family and specific real-world dataset.
- Edge curvature in model networks: In sparse ER, WS, and BA model networks, edge-curvature correlations are high but vanish as average degree increases.Hyperbolic random geometric graphs retain high correlations with weaker dependence on average degree in the explored parameter range.
- Edge curvature in real networks: In most real-world networks, augmented Forman-Ricci edge curvature has moderate to high positive correlation with Ollivier-Ricci curvature.This includes networks where ordinary Forman-Ricci curvature has weak or no correlation.
- Vertex curvature: Model-network vertex curvatures show high positive correlations in ER, WS, and BA networks, with only minor dependence on network size or average degree.Hyperbolic random geometric graphs generally show moderate positive correlations.
- Vertex curvature: For vertex curvature, Spearman correlation is typically higher than Pearson in ER, WS, and BA networks, but lower than Pearson in hyperbolic random geometric graphs.
- Vertex curvature: In most real-world networks, augmented Forman-Ricci vertex curvature correlates more strongly with Ollivier-Ricci curvature than ordinary Forman-Ricci vertex curvature.
- Vertex versus edge curvature: Vertex-curvature correlations exceed edge-curvature correlations in most analyzed networks, partly because averaging shares endpoint-degree terms and reduces variance.
B. Comparison of Forman-Ricci and Ollivier-Ricci curvature with other edge-based measures
Across model and real networks, Ricci curvatures are negatively associated with edge betweenness centrality, while their relationships with embeddedness and dispersion are inconsistent.
- Ollivier-Ricci, Forman-Ricci, and Augmented Forman-Ricci curvature show significant negative correlations with edge betweenness centrality in model networks.
- In most real networks, Ollivier-Ricci curvature has moderate-to-high negative correlation with edge betweenness centrality, whereas Forman-Ricci curvature has weak-to-moderate negative correlation.
- Table I reports Spearman correlations between Ollivier-Ricci and either Forman-Ricci or Augmented Forman-Ricci edge curvatures across model and real networks.For model networks, values are means over 100 generated networks; Pearson correlations are also provided in supplementary results.
- The analyzed networks show no consistent relationship between any of the three curvature measures and embeddedness.
- The analyzed networks likewise show no consistent relationship between any of the three curvature measures and dispersion.
C. Comparison of Forman-Ricci and Ollivier-Ricci curvature with vertex-based measures
Vertex Ricci curvatures are strongly negatively correlated with degree and betweenness centrality, but show no consistent relationship with clustering coefficient.
- Table II compares Spearman correlations between Ollivier-Ricci and either Forman-Ricci or Augmented Forman-Ricci vertex curvatures in model and real networks.Model-network correlations are means over samples of 100 generated networks, with Pearson correlations additionally reported in supplementary results.
- Ollivier-Ricci, Forman-Ricci, and Augmented Forman-Ricci vertex curvatures have high negative correlations with degree in most analyzed model and real networks.Degree appears implicitly in the defining vertex-curvature formula through the sum over adjacent edges.
- All three vertex-curvature measures also have high negative correlations with betweenness centrality in model and real networks.
- None of the three vertex-curvature measures has a consistent relationship with clustering coefficient across the analyzed model and real networks.
D. Relative importance of Forman-Ricci and Ollivier-Ricci curvature for topological robustness of networks
The study evaluates network robustness by tracking communication efficiency after targeted edge or vertex removal. Negative Ollivier-Ricci curvature identifies elements whose removal generally causes faster large-scale disintegration than competing criteria.
- Communication efficiency quantifies how removing edges or vertices affects large-scale network connectivity.It captures resilience to perturbations through local clustering and the inverse of characteristic path length.
- Edges are removed randomly, by increasing Ricci curvature, or by decreasing edge betweenness centrality to compare their effects on connectivity.The curvature criteria include Forman-Ricci, Augmented Forman-Ricci, and Ollivier-Ricci curvature.
- Figure 2 plots communication efficiency against the fraction of removed edges for four model networks and four real networks.The networks are ER, WS, BA, HGG, US Power Grid, yeast protein interactions, Euro road, and email communication.
- Figure 3 plots communication efficiency against the fraction of removed vertices for the same four model and four real networks.
- Removing edges in increasing Ollivier-Ricci curvature order typically causes at least slightly faster disintegration than removal based on other measures.
- Vertices with highly negative Ollivier-Ricci curvature are more important for maintaining large-scale connectivity than vertices with highly negative Forman-Ricci curvature in most analyzed networks.
V. CONCLUSIONS
The paper compares Ollivier-Ricci and Forman-Ricci curvature as distinct network-geometric measures. Their different theoretical bases yield different encoded properties, despite the paper’s broader empirical comparison of the two discretizations.
- The study empirically investigates Ollivier-Ricci and Forman-Ricci curvature across model and real-world networks.
- The two discretizations derive from different theoretical considerations and convey insights into different geometrical properties and network behaviors.
- Ollivier-Ricci curvature captures clustering and coherence, whereas Forman-Ricci curvature captures dispersal and topology.
- In weighted networks, Ollivier-Ricci curvature treats edge weights as probabilities, while Forman-Ricci curvature treats edge weights as lengths and vertex weights as concentrated area measures.
- An independent preprint comparing the two discretizations in biological networks appeared while the manuscript was in its final submission stages.