Scale-free networks are ultrasmall

被引:493
作者
Cohen, R [1 ]
Havlin, S
机构
[1] Bar Ilan Univ, Minerva Ctr, Ramat Gan, Israel
[2] Bar Ilan Univ, Dept Phys, Ramat Gan, Israel
关键词
D O I
10.1103/PhysRevLett.90.058701
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k)proportional tok(-lambda), i.e., the probability of having k links outgoing from a site. In contrast to the diameter of regular random networks or small-world networks, which is known to be dsimilar tolnN, we show, using analytical arguments, that scale-free networks with 2<lambda<3 have a much smaller diameter, behaving as dsimilar tolnlnN. For lambda=3, our analysis yields dsimilar tolnN/lnlnN, as obtained by Bollobas and Riordan, while for lambda>3, dsimilar tolnN. We also show that, for any lambda>2, one can construct a deterministic scale-free network with dsimilar tolnlnN, which is the lowest possible diameter.
引用
收藏
页数:4
相关论文
共 28 条
  • [1] Search in power-law networks
    Adamic, L.A.
    Lukose, R.M.
    Puniyani, A.R.
    Huberman, B.A.
    [J]. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 2001, 64 (4 II): : 461351 - 461358
  • [2] Aiello W., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P171, DOI 10.1145/335305.335326
  • [3] Internet -: Diameter of the World-Wide Web
    Albert, R
    Jeong, H
    Barabási, AL
    [J]. NATURE, 1999, 401 (6749) : 130 - 131
  • [4] Emergence of scaling in random networks
    Barabási, AL
    Albert, R
    [J]. SCIENCE, 1999, 286 (5439) : 509 - 512
  • [5] Extremal properties of random trees
    Ben-Naim, E
    Krapivsky, PL
    Majumdar, SN
    [J]. PHYSICAL REVIEW E, 2001, 64 (03): : 4
  • [6] Bose-Einstein condensation in complex networks
    Bianconi, G
    Barabási, AL
    [J]. PHYSICAL REVIEW LETTERS, 2001, 86 (24) : 5632 - 5635
  • [7] Bollobas B, 2002, HDB GRAPHS NETWORKS
  • [8] Bollobas B., 2001, CAMBRIDGE STUDIES AD, V73
  • [9] Graph structure in the Web
    Broder, A
    Kumar, R
    Maghoul, F
    Raghavan, P
    Rajagopalan, S
    Stata, R
    Tomkins, A
    Wiener, J
    [J]. COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING, 2000, 33 (1-6): : 309 - 320
  • [10] The average distances in random graphs with given expected degrees
    Chung, F
    Lu, LY
    [J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (25) : 15879 - 15882