Navigation on Power-Law Small World Network with Incomplete Information

• 来源期刊: 中国物理快报（英文版）
• 年，卷（期）: 2007,（3）
• 页码范围: 839-842
• 页数: 4页
• 语种: 英文

摘要

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 β depends 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.