Navigation on Power-Law Small World Network with Incomplete Information

We investigate the navigation process on a variant of the Watts--Strogatz small-world network model with local information. In the network construction, each vertex of an N×N square lattice sends out a long-range link with probability p. The other end of the link falls on a randomly chosen vertex with probability proportional to r-α, where r is the lattice distance
between the two vertices, and α≥0. The average actual path length, i.e. the expected number of steps for passing messages between randomly chosen vertex pairs, is found to scale as a power-law function of the network size N^β, except when α is close to a specific value α_min, which gives the highest efficiency of message navigation. For a finite network, the exponent β epends on both α and p, and α_min drops to zero at a critical value of p which depends on N. When the network size goes to infinity, β depends only on α, and α_min is equal to the network dimensionality.