Navigating ultrasmall worlds in ultrashort time

Abstract

Random scale-free networks are ultrasmall worlds. The average length of the shortest paths in networks of size N scales as lnlnN. Here we show that these ultrasmall worlds can be navigated in ultrashort time. Greedy routing on scale-free networks embedded in metric spaces finds paths with the average length scaling also as lnlnN. Greedy routing uses only local information to navigate a network. Nevertheless, it finds asymptotically the shortest paths, a direct computation of which requires global topology knowledge. Our findings imply that the peculiar structure of complex networks ensures that the lack of global topological awareness has asymptotically no impact on the length of communication paths. These results have important consequences for communication systems such as the Internet, where maintaining knowledge of current topology is a major scalability bottleneck.

4 pages, 2 figures

References in corpus (8)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Evolution of networks
• Scale-Free Networks are Ultrasmall
• Navigability of Complex Networks
• Class of correlated random networks with hidden variables
• Self-similarity of complex networks and hidden metric spaces
• Metric structure of random networks

Cited by in corpus (23)

• Network Geometry
• Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces
• Designing optimal transport networks
• The hidden geometry of weighted complex networks
• Extended navigability of small world networks: exact results and new insights
• Asymptotic behavior of the Kleinberg model
• Non-consensus opinion models on complex networks
• Superlinear and sublinear urban scaling in geographical network model of the city
• Critical fluctuations in spatial complex networks
• Scaling of human behavior during portal browsing
• Modeling Structure and Resilience of the Dark Network
• Exploring Maps with Greedy Navigators
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Strategy of Competition between Two Groups based on a Contrarian Opinion Model
• Hidden Variables in Bipartite Networks
• Scale-free networks embedded in fractal space
• New Phenomena in Large-Scale Internet Traffic
• Random hyperbolic graphs in $d+1$ dimensions
• Self-organized Emergence of Navigability on Small-World Networks
• Pathlength scaling in graphs with incomplete navigational information
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• High Performance Algorithms for Quantum Gravity and Cosmology
• Hidden space reconstruction inspires link prediction in complex networks