Euclidean versus hyperbolic congestion in idealized versus experimental networks

Abstract

This paper proposes a mathematical justification of the phenomenon of extreme congestion at a very limited number of nodes in very large networks. It is argued that this phenomenon occurs as a combination of the negative curvature property of the network together with minimum length routing. More specifically, it is shown that, in a large n-dimensional hyperbolic ball B of radius R viewed as a roughly similar model of a Gromov hyperbolic network, the proportion of traffic paths transiting through a small ball near the center is independent of the radius R whereas, in a Euclidean ball, the same proportion scales as 1/R^{n-1}. This discrepancy persists for the traffic load, which at the center of the hyperbolic ball scales as the square of the volume, whereas the same traffic load scales as the volume to the power (n+1)/n in the Euclidean ball. This provides a theoretical justification of the experimental exponent discrepancy observed by Narayan and Saniee between traffic loads in Gromov-hyperbolic networks from the Rocketfuel data base and synthetic Euclidean lattice networks. It is further conjectured that for networks that do not enjoy the obvious symmetry of hyperbolic and Euclidean balls, the point of maximum traffic is near the center of mass of the network.

23 pages, 4 figures

References in corpus (2)

• The Large Scale Curvature of Networks
• Curvature and temperature of complex networks

Cited by in corpus (27)

• Sustaining the Internet with Hyperbolic Mapping
• Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
• From the betweenness centrality in street networks to structural invariants in random planar graphs
• Interdisciplinary and physics challenges of Network Theory
• Emergent Complex Network Geometry
• Dynamic Network Centrality Summarizes Learning in the Human Brain
• Topological implications of negative curvature for biological and social networks
• Complex Quantum Network Geometries: Evolution and Phase Transitions
• Ollivier-Ricci curvature convergence in random geometric graphs
• Hyperbolicity Measures "Democracy" in Real-World Networks
• The inherent community structure of hyperbolic networks
• Ricci Curvature of the Internet Topology
• Model-independent methods for embedding directed networks into Euclidean and hyperbolic spaces
• Betweenness centrality in dense spatial networks
• Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
• Optimisation of the coalescent hyperbolic embedding of complex networks
• Obstructions to a small hyperbolicity in Helly graphs
• Quantum networks: Anti-core of spin chains
• On the Hyperbolicity of Small-World and Tree-Like Random Graphs
• Traffic Congestion in Expanders, $(p,\delta )$--Hyperbolic Spaces and Product of Trees
• Geometry and Curvature of Spin Networks
• A Geometric Distance Oracle for Large Real-World Graphs
• Scaling of Congestion in Small World Networks
• Information Transfer Fidelity in Spin Networks and Ring-based Quantum Routers
• Traffic Analysis in Random Delaunay Tessellations and Other Graphs
• Asymptotic Traffic Flow in a Hyperbolic Network: Non-uniform Traffic
• Congestion in networks and manifolds, and fair-division problems