Universal behavior of load distribution in scale-free networks

被引:947
作者
Goh, KI [1 ]
Kahng, B
Kim, D
机构
[1] Seoul Natl Univ, Sch Phys, Seoul 151747, South Korea
[2] Seoul Natl Univ, Ctr Theoret Phys, Seoul 151747, South Korea
关键词
D O I
10.1103/PhysRevLett.87.278701
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
We study a problem of data packet transport in scale-free networks whose degree distribution follows a power law with the exponent gamma. Load, or "betweenness centrality," of a vertex is the accumulated total number of data packets passing through that vertex when every pair of vertices sends and receives a data packet along the shortest path connecting the pair. It is found that the load distribution follows a power law with the exponent delta approximate to 2.2(1), insensitive to different values of gamma in the range, 2<y<less than or equal to>3, and different mean degrees, which is valid for both undirected and directed cases. Thus, we conjecture that the load exponent is a universal quantity to characterize scale-free networks.
引用
收藏
页码:278701 / 278701
页数:4
相关论文
共 24 条
[1]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[2]   Classes of small-world networks [J].
Amaral, LAN ;
Scala, A ;
Barthélémy, M ;
Stanley, HE .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (21) :11149-11152
[3]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[4]  
BARABASI AL, CONDMAT0104162
[5]   Graph structure in the Web [J].
Broder, A ;
Kumar, R ;
Maghoul, F ;
Raghavan, P ;
Rajagopalan, S ;
Stata, R ;
Tomkins, A ;
Wiener, J .
COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING, 2000, 33 (1-6) :309-320
[6]   Souped-up search engines [J].
Butler, D .
NATURE, 2000, 405 (6783) :112-115
[7]   Structure of growing networks with preferential linking [J].
Dorogovtsev, SN ;
Mendes, JFF ;
Samukhin, AN .
PHYSICAL REVIEW LETTERS, 2000, 85 (21) :4633-4636
[8]  
ERDOS P, 1960, B INT STATIST INST, V38, P343
[9]  
Faloutsos M, 1999, COMP COMM R, V29, P251, DOI 10.1145/316194.316229
[10]   SET OF MEASURES OF CENTRALITY BASED ON BETWEENNESS [J].
FREEMAN, LC .
SOCIOMETRY, 1977, 40 (01) :35-41