Extended navigability of small world networks: exact results and new insights

Abstract

Navigability of networks, that is the ability to find any given destination vertex starting from any other vertex, is crucial to their usefulness. In 2000 Kleinberg showed that optimal navigability could be achieved in small-world networks provided that a special recipe was used to establish long range connections, and that a greedy algorithm, that ensures that the destination will be reached, is used. Here we provide an exact solution for the asymptotic behavior of such a greedy algorithm as a function of the system's parameters. Our solution enables us to show that the original claim that only a very special construction is optimal can be relaxed depending on further criteria, such as, for example, cost minimization, that must be satisfied.

Presented at the BCNet Workshop in Barcelona on December 12 2008; submitted to PRL

References in corpus (4)

• Navigability of Complex Networks
• Physical realizability of small-world networks
• Asymptotic behavior of the Kleinberg model
• Navigating ultrasmall worlds in ultrashort time

Cited by in corpus (19)

• Spatial Networks
• Small-world behavior in time-varying graphs
• Assessing the relevance of node features for network structure
• Designing optimal transport networks
• Navigable Networks as Nash Equilibria of Navigation Games
• Explicit determination of mean first-passage time for random walks on deterministic uniform recursive trees
• Annealed and Mean-Field formulations of Disease Dynamics on Static and Adaptive Networks
• Asymptotic behavior of the Kleinberg model
• Local Empathy provides Global Minimization of Congestion in Communication Networks
• Exact Solution for Optimal Navigation with Total Cost Restriction
• Robustness of Spatial Micronetworks
• SWFC-ART: A Cost-effective Approach for Fixed-Size-Candidate-Set Adaptive Random Testing through Small World Graphs
• Dynamics on Spatial Networks and the Effect of Distance Coarse Graining
• Greedy Connectivity of Geographically Embedded Graphs
• On the decentralized navigation of multiple packages on transportation networks
• Degree heterogeneity in spatial networks with total cost constraint
• Universality of critical dynamics on a complex network
• Competition and evolution in restricted space
• Navigation in non-uniform density social networks