Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces

Abstract

We show that complex (scale-free) network topologies naturally emerge from hyperbolic metric spaces. Hyperbolic geometry facilitates maximally efficient greedy forwarding in these networks. Greedy forwarding is topology-oblivious. Nevertheless, greedy packets find their destinations with 100% probability following almost optimal shortest paths. This remarkable efficiency sustains even in highly dynamic networks. Our findings suggest that forwarding information through complex networks, such as the Internet, is possible without the overhead of existing routing protocols, and may also find practical applications in overlay networks for tasks such as application-level routing, information sharing, and data distribution.

References in corpus (6)

• Hierarchical structure and the prediction of missing links in networks
• Vertex similarity in networks
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• On Compact Routing for the Internet
• Curvature and temperature of complex networks
• Navigating ultrasmall worlds in ultrashort time

Cited by in corpus (25)

• Popularity versus Similarity in Growing Networks
• Sustaining the Internet with Hyperbolic Mapping
• Network Geometry
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Hidden geometric correlations in real multiplex networks
• An Experimental Investigation of Hyperbolic Routing with a Smart Forwarding Plane in NDN
• Navigable Networks as Nash Equilibria of Navigation Games
• Average Distance in a General Class of Scale-Free Networks with Underlying Geometry
• Ricci Curvature of the Internet Topology
• Collective navigation of complex networks: Participatory greedy routing
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Not all interventions are equal for the height of the second peak
• Effect of Gromov-hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications
• Fast and Scalable Analysis of Massive Social Graphs
• On the Hyperbolicity of Small-World and Tree-Like Random Graphs
• Greedy Routing and the Algorithmic Small-World Phenomenom
• Organic Design of Massively Distributed Systems: A Complex Networks Perspective
• Hyperbolic Deep Learning for Foundation Models: A Survey
• Fast generation of complex networks with underlying hyperbolic geometry
• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs
• A Game Theoretic Model for the Formation of Navigable Small-World Networks --- the Tradeoff between Distance and Reciprocity
• Symmetry-driven embedding of networks in hyperbolic space
• Enumeration of graphs with a heavy-tailed degree sequence
• Spectral analysis of communication networks using Dirichlet eigenvalues
• Dovetail: Stronger Anonymity in Next-Generation Internet Routing