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.
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.
CHEN Jian-Zhen;ZHU Jian-Yang. Navigation on Power-Law Small World Network with Incomplete Information[J]. 中国物理快报, 2007, 24(3): 839-842.
CHEN Jian-Zhen, ZHU Jian-Yang. Navigation on Power-Law Small World Network with Incomplete Information. Chin. Phys. Lett., 2007, 24(3): 839-842.
[1] Brin S and Page L 1998 Computer Networks 30 107 [2] Kleinberg J M 1999 J. Associat. Comput. Machin. 46 604 [3] Kleinberg J and Lawrence S 2001 Science 294 1849 [4] Adamic L A, Lukose R M, Puniyani A R and Huberman B A 2001 Phys. Rev. E 64 046135 [5] Menczer F and Belew R K 2000 Machine Learning 39203 [6] Kim B J, Yoon C N, Han S K and Jeong H 2002 Phys. Rev.E 65 027103 [7] Watts D J, Dodds P S and Newman M E J 2002 Science 296 1302 [8] Thadakamalla H P, Albert R and Kumara S R T 2005 Phys.Rev. E 72 066128 [9] de Moura A P S, Motter A E and Grebogi C 2003 Phys.Rev. E 68 036106 [10] Kleinberg J M 2000 Nature 406 845 [11] Neman M E J 2003 SIAM Rev. 45 167 [12] Milgram S 1967 Psychology Today 2 60 [13] Dodds P S, Muhamad R and Watts D J 2003 Science 301 827 [13] Strogatz S H 2001 Nature 410 268 Albert R and Barabasi A -L 2002 Rev. Mod. Phys. 74 47 [14] Zhu H and Huang Z X 2004 Phys. Rev. E 70 036117 [15] Chen J Z, Liu W and Zhu J Y 2006 Phys. Rev. E 73056111 [16] Watts D J and Strogatz S H 1998 Nature 393 440 [17] Newman M E J and Watts D J 1999 Phys. Rev. E 60 7332 [18] Nguyen V and Martel C 2005 Proceedings of theSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms p 311 [19] Kozma B, Hastings M B and Korniss G 2005 Phys. Rev.Lett. 95 018701 [20] Jespersen s and Blumen A 2000 Phys. Rev. E 62 6270 [21] Barabasi A L and Albert R 1999 Science 286 509 Dorogovtsev S N and Mends J F F 2001 Phys. Rev. E 6306125 [22] Braunstein L A, Buldyrev S V, Cohen R, Havlin S and Stanley HE 2003 Phys. Rev. Lett. 91 168701 Cieplak M, Maritan A and Banavar J R 1996 Phys. Rev. Lett. 76 3754 [23] Albert R, Jeony H and Barabasi A -L 1999 Nature 401 130 Newman M E J 2001 Phys. Rev. E 64 016132; Chung f and Lu L 2002 Proc. Natl. Acad. Sci. USA 9915879 [24] Press W H, Teukolsky S A, Vetterling W T and Flannery B P2002 Numerical Recipes in C++: The Art of Scientific Computing 2ndedn (Cambridge: Cambridge University Press) [25] Bunde a and Havlin S 1991 Fractals and DisorderedSystem (Berlin: Springer) and references therein [26] Sen P, Banerjee K and Biswas T 2002 Phys. Rev. E 66 037102
2007, Vol. 24 
