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 x 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 value, which gives the highest efficiency of message navigation. For a finite network, the exponent β depends on both α and p, and p αmin drops to zero at a critical value of p which depends on N. When the network size goes to infinity,β depends only only on α, and αmin is equal to the network dimensionality.