| Original Articles |
|
|
|
|
Navigation on Power-Law Small World Network with Incomplete Information |
| CHEN Jian-Zhen 1,2;ZHU Jian-Yang1 |
| 1Department of Physics, Beijing Normal University, Beijing 1008752Department of Physics, Jiangxi Normal University, Nanchang 330027 |
|
| Cite this article: |
|
CHEN Jian-Zhen, ZHU Jian-Yang 2007 Chin. Phys. Lett. 24 839-842 |
|
|
|
|
Abstract 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.
|
| Keywords:
89.75.Hc
84.35.+i
87.23.Ge
89.20.Hh
|
|
|
Received: 01 August 2006
Published: 08 February 2007
|
|
|
|
|
|
|
|
[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 |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
