Source-linked AI summary
Ricci Curvature of the Internet Topology
Chien-Chun Ni, Yu-Yao Lin, Jie Gao, Xianfeng David Gu, Emil Saucan
TL;DR
Prior work characterized Internet topology with worst-case hyperbolicity, while local curvature structure and its network connections remained a question. This paper analyzes coarse Ricci curvature across Internet data and reports broad curvature variation, with distributions differing across topology types.
Problem
Prior hyperbolicity measures capture worst-case metric properties, leaving open whether local geometric structure connects to network behavior at finer scale.
Source: A. Prior Work · p. 2Method
The paper computes coarse Ricci curvature across Internet topologies and examines its connections to graph properties and geographical and IP distances.
Source: C. Contribution · p. 3, F. Curvature vs. Geographical and IP… · p. 7Results
Curvature distributions show broad spread and differ across Internet topology types, while curvature has varied connections to local and auxiliary properties.
Source: C. Contribution · p. 3Takeaways & Limitations
The observed curvature variation suggests studying Internet topology at finer granularity and considering non-homogeneous spaces for its embedding.
Source: §VI · p. 8The datasets may be incomplete and lack application-relevant edge weights such as delay, bandwidth, and routing policy.
Source: §VI · p. 8
Abstract
from arXiv · showhide
Analysis of Internet topologies has shown that the Internet topology has negative curvature, measured by Gromov's "thin triangle condition", which is tightly related to core congestion and route reliability. In this work we analyze the discrete Ricci curvature of the Internet, defined by Ollivier, Lin, etc. Ricci curvature measures whether local distances diverge or converge. It is a more local measure which allows us to understand the distribution of curvatures in the network. We show by various Internet data sets that the distribution of Ricci cuvature is spread out, suggesting the network topology to be non-homogenous. We also show that the Ricci curvature has interesting connections to both local measures such as node degree and clustering coefficient, global measures such as betweenness centrality and network connectivity, as well as auxilary attributes such as geographical distances. These observations add to the richness of geometric structures in complex network theory.
I. INTRODUCTION
Internet topology matters for understanding robustness, vulnerability, congestion control, and virus diffusion. Prior work characterized global hyperbolicity, while this paper asks whether finer-scale local curvature reveals additional structure.
I. INTRODUCTION
- Internet topology has been studied at router, autonomous-system, and application-overlay levels because its structure relates to robustness, vulnerability, congestion control, and virus diffusion.Source: §I · p. 1
A. Prior Work
- Traffic measurements and shortest-path routing studies motivated the view that Internet routes concentrate through a relatively small core, suggesting negative global curvature.Source: A. Prior Work · p. 1
- Gromov hyperbolicity describes networks through δ-slim geodesic triangles, but captures a worst-case metric property rather than local geometric structure.The paper frames local curvature as a way to examine network behavior at finer scale.Source: A. Prior Work · pp. 1–2
- Prior work found Rocketfuel ISP hop-count hyperbolicity values of 1–3 against network diameters mostly 12–14, and shortest-path congestion scaling consistent with hyperbolicity.The reported congestion scales in the order of N_i^2, compared with n^3/2 for Euclidean disks and n^2 for hyperbolic disks.Source: A. Prior Work · p. 2
B. Curvature
The section reviews continuum curvature concepts and explains how curvature notions extend to graphs. It presents coarse Ricci curvature as a local comparison of distances between neighboring distributions.
B. Curvature
- Gaussian curvature is the product k1k2 of a surface’s principal curvatures, with positive, negative, and zero signs associated respectively with sphere-like, saddle-like, and planar geometry.Source: B. Curvature · p. 2
- A triangulated-surface discrete curvature definition does not apply to general graphs because it requires a triangulation.Source: B. Curvature · p. 2
- Sectional curvature uses the difference between transported-vector endpoint distance and |v|, while Ricci curvature averages sectional curvature over directions w.Ricci curvature therefore depends on direction v rather than both tangent directions.Source: B. Curvature · p. 2
- Ollivier’s coarse Ricci curvature compares the distance between two small balls with the distance between their centers, using optimal transport distance between the balls.Positive curvature corresponds to the small balls being closer than their centers.Source: B. Curvature · p. 2
C. Contribution
The paper studies coarse Ricci curvature across Internet topologies and its connections to local and global graph structures, connectivity, vulnerability, and routing. It defines curvature using transport between node distributions and analyzes its computation on graphs.
C. Contribution
- Ricci curvature is widely spread across networks, with positive-curvature communities and topology-specific distributions that existing complex-network models do not fully explain.The authors also report fast computation on power-law networks.Source: C. Contribution · p. 3
- For physical ISP and AS topologies, negative-curvature edges tend to lie on shortest paths, and removing them disconnects networks quickly.Source: C. Contribution · p. 3
II. RICCI CURVATURE ON GRAPHS
- Coarse Ricci curvature compares the earth-mover distance between node distributions with the distance between the corresponding nodes.Positive curvature indicates that the distributions are closer than their centers.Source: §II · p. 3
- Vertex curvature is defined as the average curvature of its adjacent edges, and the analyzed datasets use unit-weight edges because detailed link information is unavailable.Source: §II · p. 3
- The curvature computation uses linear programming to find a mass-preserving transport plan minimizing total travel distance, based on shortest-path lengths between the endpoints’ neighbors.The required neighbor-to-neighbor distances are local, which the authors say makes computation scalable.Source: §II · p. 3
III. NETWORKS AND DATASETS
The datasets cover Internet networks at several levels and a power-grid network for comparison. They include physical, logical, and social connections.
III. NETWORKS AND DATASETS
- The study analyzes AS-level, router-level, peer-to-peer, and PGP networks, alongside a power-grid network as a structurally different comparison.Source: §III · pp. 3–4
- AS-level links represent inter-domain connections, router-level links physical connections, and peer-to-peer links logical overlay connections.Source: §III · p. 4
- The PGP network records user interactions, while the power-grid dataset represents Western US power lines and nodes such as generators, transformers, and substations.Source: §III · p. 4
A. Running Time Analysis
The authors analyze the cost of computing discrete Ricci curvature on Internet topologies. Under a power-law degree assumption, the expected per-edge cost is constant, so computing all edge curvatures scales linearly with the number of edges.
A. Running Time Analysis
- For edge xy, the LP solver cost is linear in kx · ky, where kx and ky are the endpoint degrees.The LP solver dominates the running time.Source: A. Running Time Analysis · p. 4
- With degree exponent γ between 2 and 3, the expected per-edge running time is constant under the stated independent-degree assumption.The analysis assumes the LP solver takes O(kxky) time.Source: A. Running Time Analysis · p. 4
- Computing all Ricci curvatures scales linearly with the number of network edges under the analyzed degree assumptions.The authors describe this cost as suitable for large-scale networks.Source: A. Running Time Analysis · p. 4
B. Curvature Distribution
Ricci curvature distributions vary across Internet topology datasets, while edge curvature is also related to network connectivity and global centrality measures. Removing the most negatively curved edges can sharply reduce connectivity, unlike random edge removal.
B. Curvature Distribution
- Curvature distributions vary with α in spread but retain their general shape; AS and router distributions are similar, whereas Gnutella is concentrated at negative curvature and PGP has more positive edges.The authors note that these differences cannot be explained by a single generative graph model, even when networks share properties such as power-law degree.Source: B. Curvature Distribution · p. 5, Figure 6 · p. 5
C. Curvature vs. Graph Connectivity
- The authors relate edge curvature to global network connectivity, despite negative curvature's local interpretation of an edge as a shortcut.The graph-connectivity experiments examine component counts as edges are added in curvature order.Source: C. Curvature vs. Graph Connectivity · p. 5
- Adding edges in increasing-curvature order keeps component counts small, while decreasing-curvature order can produce many components, peaking as curvature passes zero.The authors report the same behavior pattern in four other network types, except Gnutella, whose cutoff shifts left; backbone routers are negatively curved.Source: C. Curvature vs. Graph Connectivity · p. 5
- Removing the 20% most negatively curved edges splits the largest connected component into two, while random removal degrades it steadily until 80% of edges are removed.The targeted-removal curve shows a deep drop at the split; random removal is described as maintaining connectivity until most edges are gone.Source: C. Curvature vs. Graph Connectivity · pp. 5–6
- Smaller edge curvature generally accompanies higher betweenness, but the correlation is weak; farness has a linear trend only for router topology and weak or no correlation elsewhere.Betweenness and farness are global measures whose computation scales as O(nm).Source: C. Curvature vs. Graph Connectivity · p. 6
E. Curvature vs. Local Properties
The section compares Ricci curvature with node degree, clustering coefficient, and centrality measures, finding weak node-level associations with degree and clustering.
E. Curvature vs. Local Properties
- Curvature has a weak correlation with node degree across five networks.Although Ricci curvature is computed mainly from neighboring nodes, degree is only weakly correlated with it.Source: E. Curvature vs. Local Properties · p. 6
- Figures compare curvature with betweenness and farness centrality across networks, and with several measures for Exodus(US).The supplied figure descriptions identify the comparisons but do not state their outcomes.Source: Figure 9 · p. 6, Figure 11 · p. 6, Figure 10 · p. 6
- Although bounds relating clustering coefficient to Ricci curvature are proved, Figures 10(c) and 13 show that their correlation on nodes is rather weak.Source: E. Curvature vs. Local Properties · p. 7
F. Curvature vs. Geographical and IP Distances
In Rocketfuel data, positively curved edges tend to be geographically short, while negatively curved edges show no special pattern and IP distance shows no correlation.
F. Curvature vs. Geographical and IP Distances
- Positively curved Rocketfuel edges tend to be geographically short, while negatively curved edges show no special pattern and IP distance has no apparent correlation with curvature.The comparison uses geographic locations and IP addresses available for some routers in the Rocketfuel data sets.Source: F. Curvature vs. Geographical and IP… · p. 7
V. MODEL NETWORKS
Model-network comparisons show that curvature distributions and connectivity behavior vary by model; configuration, Barabási–Albert, and H(3, 7) models resemble real-world connectivity patterns.
V. MODEL NETWORKS
- The study examines G(n, p) with n=1000 and p=0.01, plus a configuration model using the power-law degree sequence of the Exodus(US) router graph.Table III lists graph properties for the model networks.Source: §V · p. 7, Table III · p. 8
- The W-S model uses (n, k, β)=(1000, 8, 0.5), and the B-A model uses (n, k)=(1000, 2).W-S rewires ring edges with probability β; B-A adds nodes whose edge endpoints are chosen in proportion to current degree.Source: §V · p. 7
- The random regular graph uses (n, d)=(1000, 8), while the hyperbolic-grid example is a finite H(3, 7) subgraph.Each H(3, 7) node is surrounded by seven triangles.Source: §V · p. 7
- G(n, p) and random regular graphs have more negatively curved edges than AS and router-level topologies, while W-S, configuration, and B-A distributions are closer to AS but lack many zero-curvature edges.The comparison also includes the Gnutella topology, which is closer to G(n, p) and random regular graphs.Source: §V · p. 7, Figure 15 · p. 8
- Configuration, B-A, and H(3, 7) models share connectivity behavior with real-world data; G(n, p), random regular, and W-S models produce many disconnected components under either edge-removal order.The authors suggest small diameter is less relevant to this behavior than graph hyperbolicity and power-law degree distribution.Source: §V · p. 8, Figure 16 · p. 8
VI. DISCUSSION AND FUTURE WORK
The discussion cautions that incomplete, unweighted data constrain the study, while its curvature findings motivate heterogeneous geometric embeddings and further work on Internet topology models and design.
VI. DISCUSSION AND FUTURE WORK
- Incomplete data constrain the analysis: the AS graph omits many non-tree peer links, and studied data sets lack application-relevant edge weights such as delay, bandwidth, and routing policy.The authors state that curvature can be computed and updated when additional weight information becomes available.Source: §VI · p. 8
- Because negatively curved metrics cannot be isometrically embedded in fixed-dimensional Euclidean spaces, the authors suggest this may help explain prior Euclidean embedding errors and improved hyperbolic-embedding performance.The discussion describes further exploration of this direction in –.Source: §VI · p. 8
- The observed curvature variation suggests exploring non-homogeneous spaces, such as Riemannian manifolds, for embeddings that accommodate Internet-graph heterogeneity.The authors also identify explaining the reported distributions and developing generative graph models as open questions.Source: §VI · pp. 8–9
- The authors propose that geometric analysis could inform future topology changes aimed at improving efficiency, reducing vulnerability, or reducing congestion.They suggest formulating a desirable Ricci-curvature distribution and examining topology and link-weight changes to achieve it.Source: §VI · p. 9