The volume of the giant component of a random graph with given expected degrees

被引:50
作者
Chung, Fan [1 ]
Lu, Linyuan
机构
[1] Univ Calif San Diego, Dept Math, San Diego, CA 92093 USA
[2] Univ S Carolina, Dept Math, Columbia, SC 29208 USA
关键词
random graphs; expected degree sequences; giant connected component;
D O I
10.1137/050630106
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We consider the random graph model G(w) for a given expected degree sequence w = (w(1), w(2),..., w(n)). If the expected average degree is strictly greater than 1, then almost surely the giant component in G of G( w) has volume ( i.e., sum of weights of vertices in the giant component) equal to lambda(0)Vol(G) + O(root n log(3.5) n), where lambda(0) is the unique nonzero root of the equation Sigma(n)(i-1) w(i)e(-wi lambda) = (1-lambda) Sigma(n)(i=1) w(i), and where Vol(G) = Sigma(i) w(i).
引用
收藏
页码:395 / 411
页数:17
相关论文
共 26 条
[1]  
Aiello W, 2002, MASSIVE COMP, V4, P97
[2]  
Aiello W., 2000, Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, P171, DOI 10.1145/335305.335326
[3]   A random graph model for power law graphs [J].
Aiello, W ;
Chung, F ;
Lu, LY .
EXPERIMENTAL MATHEMATICS, 2001, 10 (01) :53-66
[4]   Error and attack tolerance of complex networks [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 2000, 406 (6794) :378-382
[5]  
[Anonymous], P 19 ACM SIGMOD SIGA
[6]  
[Anonymous], INT MATH
[7]   Scale-free characteristics of random networks:: the topology of the World-Wide Web [J].
Barabási, AL ;
Albert, R ;
Jeong, H .
PHYSICA A, 2000, 281 (1-4) :69-77
[8]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[9]  
Bollobas B, 2003, INTERNET MATH, V1, P1, DOI DOI 10.1080/15427951.2004.10129080
[10]   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