Ricci Curvature of the Internet Topology

Abstract

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.

arXiv comment9 pages, 16 figures. To be appear on INFOCOM 2015

References in corpus (9)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Community structure in social and biological networks
• The Dynamics of Viral Marketing
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• The Large Scale Curvature of Networks
• Euclidean versus hyperbolic congestion in idealized versus experimental networks
• DIMES: Let the Internet Measure Itself
• Ollivier's Ricci curvature, local clustering and curvature dimension inequalities on graphs

Cited by in corpus (11)

• Systematic evaluation of a new combinatorial curvature for complex networks
• Discrete Ricci curvatures for directed networks
• Quantum geometry of correlated many-body states
• An estimate of the first non-zero eigenvalue of the Laplacian by the Ricci curvature on edges of graphs
• Ricci-flat graphs with girth four
• Forman-Ricci flow for change detection in large dynamic data sets
• Augmenting the User-Item Graph with Textual Similarity Models
• Ollivier persistent Ricci curvature (OPRC) based molecular representation for drug design
• Exact Expressions and Reduced Linear Programmes for the Ollivier Curvature in Graphs
• Network Alignment by Discrete Ollivier-Ricci Flow
• Characterizing Physician Referral Networks with Ricci Curvature