Two-dimensional small-world networks: navigation with local information

Abstract

Navigation process is studied on a variant of the Watts-Strogatz small world network model embedded on a square lattice. With probability $p$, each vertex sends out a long range link, and the probability of the other end of this link falling on a vertex at lattice distance $r$ away decays as $r^{-\alpha }$. Vertices on the network have knowledge of only their nearest neighbors. In a navigation process, messages are forwarded to a designated target. For $\alpha <3$ and $\alpha \ne 2$, a scaling relation is found between the average actual path length and $pL$, where $L$ is the average length of the additional long range links. Given $pL>1$, dynamic small world effect is observed, and the behavior of the scaling function at large enough $pL$ is obtained. At $\alpha =2$ and 3, this kind of scaling breaks down, and different functions of the average actual path length are obtained. For $\alpha >3$, the average actual path length is nearly linear with network size.

Accepted for publication in Phys. Rev. E

References in corpus (14)

• Statistical mechanics of complex networks
• The diameter of the world wide web
• Who is the best connected scientist? A study of scientific coauthorship networks
• Search in Power-Law Networks
• Identity and Search in Social Networks
• Mean-field solution of the small-world network model
• Topology of the conceptual network of language
• Efficiency of informational transfer in regular and complex networks
• Optimal Paths in Disordered Complex Networks
• Path finding strategies in scale-free networks
• Small-World Networks: Links with long-tailed distributions
• Phase transitions in a network with range dependent connection probability
• Navigating Networks with Limited Information
• Navigation in a small world with local information

Cited by in corpus (2)

• Asymptotic behavior of the Kleinberg model
• Greedy Connectivity of Geographically Embedded Graphs