Source-linked AI summary
Forman curvature for complex networks
R. P. Sreejith, Karthikeyan Mohanraj, Jürgen Jost, Emil Saucan, Areejit Samal
TL;DR
The paper addresses how Ricci curvature can characterize undirected complex networks without the computational burden of Ollivier-Ricci curvature. It adapts Forman’s discretization to weighted and unweighted networks and finds predominantly negative curvature, distributional differences across network types, associations with degree and centrality rather than clustering, and vulnerability to targeted removal of highly negatively curved nodes.
Problem
Characterizing network geometry requires discrete curvature measures, while Ollivier-Ricci curvature can be computationally intensive for very large networks.
Method
The paper adapts Forman’s Ricci-curvature discretization to undirected weighted and unweighted networks and analyzes model and real-world networks.
Results
Most nodes and edges have negative curvature; distributions are narrow in random and small-world networks but broad in scale-free and real-world networks, with stronger associations to degree and centrality than clustering.
Takeaways & Limitations
Targeted deletion of nodes with highly negative Forman curvature rapidly disintegrates both model and real networks, suggesting curvature can reveal network organization and vulnerable nodes.
Abstract
from arXiv · showhide
We adapt Forman's discretization of Ricci curvature to the case of undirected networks, both weighted and unweighted, and investigate the measure in a variety of model and real-world networks. We find that most nodes and edges in model and real networks have a negative curvature. Furthermore, the distribution of Forman curvature of nodes and edges is narrow in random and small-world networks, while the distribution is broad in scale-free and real-world networks. In most networks, Forman curvature is found to display significant negative correlation with degree and centrality measures. However, Forman curvature is uncorrelated with clustering coefficient in most networks. Importantly, we find that both model and real networks are vulnerable to targeted deletion of nodes with highly negative Forman curvature. Our results suggest that Forman curvature can be employed to gain novel insights on the organization of complex networks.
I. INTRODUCTION
The paper motivates discrete curvature as a way to characterize network geometry and introduces Forman curvature as a computationally simple, flexible alternative for undirected networks.
- Network theory seeks to characterize network structure and structure-function relationships across biological, transportation, and social systems.
- Discrete curvature provides a geometric measure of how network-like objects deviate from flatness.
- Ricci curvature is more versatile for graph-theoretic discretizations than sectional curvature, despite being more abstract and less intuitive.
- Ollivier-Ricci curvature is computationally intensive because it requires Wasserstein distance calculations through linear programming, limiting use on very large networks.
- Forman curvature is introduced for undirected networks because it is simple to compute, supports weighted and unweighted networks, and applies to every edge without requiring triangles.
II. DEFINITION OF FORMAN CURVATURE FOR NETWORKS
The paper adapts Forman’s Ricci-curvature discretization to undirected networks, where curvature is naturally associated with edges and can also be extended to nodes for network analysis.
- Curvature framework: Forman curvature is introduced for undirected networks as a discretization of Ricci curvature.Its general mathematical foundation applies to regular CW complexes, including polyhedra and triangular meshes.
- Curvature framework: Edges are the primary carriers of Forman curvature because they provide the discrete analogue of vectors in the directional Ricci-curvature framework.The paper presents a one-dimensional edge-curvature formula and defines the edge and node weights involved.
- Edge formula: For an edge connecting v1 and v2, the relevant incident-edge sets exclude that edge itself when evaluating the curvature expression.These sets are denoted ev1 ∼e and ev2 ∼e in the paper.
- Node extension: Node curvature is extended from edge curvature using incident edges and node degree, enabling comparison with standard node-based network measures.The paper specifically motivates comparisons with degree and clustering coefficient.
- Scope of exposition: The paper omits a full explanation of parallel edges and the general Forman-curvature expression, directing readers to Forman’s original work and offering an intuitive appendix interpretation.This marks the mathematical exposition’s scope boundary.
III. DATASET OF MODEL AND REAL NETWORKS
The study evaluates Forman curvature across several generative network models and diverse real-world networks, using structural network measures and unit weights for unweighted cases.
- Network coverage: The analysis covers ER, WS, BA, and PLC models alongside real-world networks from infrastructure, communication, biological, social, literary, and online systems.The real-world collection includes power-grid, road, PGP, email, protein-interaction, word-adjacency, musician, Facebook, friendship, peer-to-peer, and human-protein networks.
- Model networks: ER generates random graphs through G(n, p), where n is the node count and p is the probability that each possible edge exists.This model supplies the study’s random-graph benchmark.
- Model networks: WS begins with a regular ring lattice and rewires edge endpoints with probability β, producing networks with high clustering and short average path length.Each node initially connects to its k nearest neighbors.
- Model networks: BA uses preferential attachment, so new nodes connect to existing nodes with probability proportional to their degree.Consequently, high-degree nodes acquire more edges over time than low-degree nodes.
- Model networks: PLC extends BA by adding a step that can connect a new node to a neighbor of an existing node, making triad formation more likely.It retains a scale-free power-law degree distribution while adding approximate average clustering.
- Network characterization: The study characterizes networks using degree, connectivity, path-length, clustering, and assortativity measures, assigning weight 1 to nodes and edges in unweighted networks.The reported structural measures include maximum, minimum, and average degree; connected components; largest-component size; mean shortest path; average clustering; and degree assortativity.
A. Distribution of Forman curvature in model and real networks
Forman curvature is predominantly negative across model and real networks, with narrow distributions in random and small-world models but broader distributions in scale-free and real networks. In real-network examples, highly negative curvature appears associated with hubs, bottlenecks, and selected road-network structures.
- Most nodes and edges in model networks have negative Forman curvature.
- Node and edge curvature distributions are narrow in random and small-world networks but broader in scale-free networks.
- Most nodes in real networks have negative curvature, with broad node-curvature distributions resembling those of scale-free networks.
- In the PDZ network, hubs and bottlenecks appear to have highly negative curvature, while high-degree nodes are less likely to connect directly.
- In the Euro road network, most nodes have negative curvature, and high-degree cities are more likely to connect directly because the network is positively assortative.
- Negative Forman curvature is linked in the cited geometric interpretation to exponential-type volume growth, whereas positive curvature is linked to finite diameter.
B. Forman curvature and common network measures in model and real networks
Forman curvature is generally negatively associated with degree and centrality measures across model and real networks, whereas its association with clustering coefficient is usually weak or absent.
- Degree: Node curvature is highly negatively correlated with degree in ER and WS networks, but more weakly negatively correlated in BA and PLC networks.
- Degree: In real networks, curvature–degree correlations are strongly negative in transportation and communication networks but weaker in biological networks.
- Clustering coefficient: Curvature has no correlation in ER and WS networks and only weak negative correlation in BA and PLC networks with clustering coefficient.
- Clustering coefficient: In real networks, curvature–clustering correlations are extremely weak or absent, while curvature associates more strongly with centrality measures than clustering coefficient.
- Centrality: Forman curvature is negatively correlated with betweenness centrality across model networks and considered real networks.
- Centrality: Forman curvature also shows negative associations with closeness and eigenvector centrality in model and real networks.
C. Forman curvature and topological robustness of networks
Targeted removal of nodes with highly negative Forman curvature rapidly damages network connectivity in model and real networks, although degree- and betweenness-based removal is more disruptive.
- Robustness: Targeted removal starting with the most negative-curvature nodes causes faster disintegration than random removal in real networks.
- Robustness: Removing nodes in increasing Forman-curvature order disrupts networks faster than removing nodes in decreasing clustering-coefficient order.
- Robustness: Degree- or betweenness-based targeted removal causes faster disintegration than removal ordered by increasing Forman curvature in model and real networks.
- Robustness: Highly negative-curvature nodes are more important for connectivity than high-clustering nodes but less important than high-degree or high-betweenness nodes.
D. Forman curvature and weighted networks
Forman curvature extends to positively weighted undirected networks because its definition incorporates node and edge weights. In the weighted Bible noun-occurrence network, most nodes have negative curvature and negative-curvature targeting damages connectivity faster than random removal.
- Weighted formulation: Forman curvature incorporates node and edge weights, unlike clustering coefficient, which cannot account for network weights.
- Weighted results: Most nodes in the positively weighted Bible noun-occurrence network have negative curvature, with a broad distribution including values ≤-100.
- Weighted robustness: Targeted removal of highly negative-curvature nodes causes faster disintegration than random removal in the weighted undirected Bible network.
- Weighted robustness: Removal ordered by increasing Forman curvature disrupts the weighted network faster than removal ordered by decreasing clustering coefficient.
V. SUMMARY AND CONCLUSIONS
The paper introduces Forman curvature for undirected networks and finds that its distributions, correlations, and node-removal behavior reveal structural differences and connectivity vulnerabilities across model and real networks.
- V. SUMMARY AND CONCLUSIONS: Forman curvature incorporates node and edge weights, allowing structural analysis of both unweighted and weighted undirected networks.The measure is presented as a discretization of Ricci curvature for complex networks.
- V. SUMMARY AND CONCLUSIONS: Most nodes and edges have negative curvature; distributions are narrow in random and small-world networks but broad in scale-free and real networks.The distributions can distinguish among different model and real network types.
- V. SUMMARY AND CONCLUSIONS: Forman curvature is more strongly associated with degree and centrality measures than with clustering coefficient in the analyzed networks.Clustering coefficient shows no correlation in random and small-world networks, weak negative correlation in scale-free networks, and extremely weak or no correlation in analyzed real networks.
- V. SUMMARY AND CONCLUSIONS: Both model and real networks are vulnerable to targeted removal of nodes with highly negative Forman curvature.Removing nodes in increasing Forman-curvature order causes faster disintegration than removing nodes in decreasing clustering-coefficient order.
- V. SUMMARY AND CONCLUSIONS: Forman-curvature results are qualitatively similar to prior Ollivier-curvature results, while this study spans biological, social, and communication networks.The cited Ollivier-curvature analysis was limited to communication networks among real networks.
- V. SUMMARY AND CONCLUSIONS: Forman curvature is simple to compute and can scale to very large networks, unlike Ollivier curvature's computationally intensive optimal-transport calculation.The paper identifies detailed comparative analysis of the two curvatures as a follow-up requiring substantially more effort.
- V. SUMMARY AND CONCLUSIONS: Extending Forman curvature to directed edges is necessary for properly investigating inherently directed real-world networks.Examples include the World Wide Web, metabolic networks, gene-regulatory networks, and neural networks.
- V. SUMMARY AND CONCLUSIONS: The present formula applies only to positive node and edge weights, motivating an extension for signed networks.Real-world gene-regulatory and neural networks can contain negative weights.
Appendix A: Interpretation of Forman curvature
Forman curvature is interpreted as an intrinsic, discrete curvature determined by network combinatorics and weights rather than by how the network is embedded or drawn.
- Appendix A: Interpretation of Forman curvature: Forman curvature is derived from the Bochner-Weitzenböck formula, so its geometric content is less transparent than its computational definition.The paper develops intuition by following Forman's approach from smooth manifolds to discrete networks.
- Appendix A: Interpretation of Forman curvature: Intrinsic properties do not depend on a geometric object's particular realization, whereas extrinsic properties depend on its embedding.The appendix introduces immersion, embedding, and isometric embedding to clarify this distinction.
- Appendix A: Interpretation of Forman curvature: In networks, Forman curvature depends only on the adjacency matrix and prescribed weights, not on how edges are drawn or arranged in the plane.This gives the network measure an intrinsic interpretation.
- Appendix A: Interpretation of Forman curvature: For an edge e0 in a square grid, only parallel edges sharing a parent or child contribute to intrinsic distances; edges sharing both do not.Collapsing adjacent edges toward a triangular degeneration motivates the role of parallel edges in the associated Laplacian.
- Appendix A: Interpretation of Forman curvature: In network graphs, the absence of higher-dimensional faces yields the edge-curvature formula, interpreted as flow across an edge contributed by adjacent edges.The network setting is the limiting case of the more general discrete construction.