Navigation on power-law small world network with incomplete information

作者：Chen Jian Zhen^*; Zhu Jian Yang

来源：Chinese Physics Letters, 2007, 24(3): 839-842.

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(-alpha), where r is the lattice distance between the two vertices, and alpha >= 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-beta, except when a is close to a specific value alpha(min), which gives the highest efficiency of message navigation. For a finite network, the exponent beta depends on both alpha and p, and alpha(min) drops to zero at a critical value of p which depends on N. When the network size goes to infinity, beta depends only on alpha, and alpha(min), is equal to the network dimensionality.

• 出版日期2007-3
• 单位北京师范大学; 江西师范大学