Giant strongly connected component of directed networks

被引:183
作者
Dorogovtsev, SN
Mendes, JFF
Samukhin, AN
机构
[1] Univ Porto, Fac Ciencias, Dept Fis, P-4169007 Oporto, Portugal
[2] Univ Porto, Fac Ciencias, Ctr Fis Porto, P-4169007 Oporto, Portugal
[3] AF Ioffe Phys Tech Inst, St Petersburg 194021, Russia
来源
PHYSICAL REVIEW E | 2001年 / 64卷 / 02期
关键词
D O I
10.1103/PhysRevE.64.025101
中图分类号
O35 [流体力学]; O53 [等离子体物理学];
学科分类号
070204 ; 080103 ; 080704 ;
摘要
We describe how to calculate the sizes of all giant connected components of a directed graph, including the strongly connected one. In particular, the World Wide Web is a directed network. The results are obtained for graphs with statistically uncorrelated vertices and an arbitrary joint in and out-degree distribution P(k(i),k(o)). We show that if P(k(i),k(o)) does not factorize, the relative size of the giant strongly connected component deviates from the product of the relative sizes of the giant in- and out-components. The calculations of the relative sizes of all the giant components are demonstrated using the simplest examples. We explain that the giant strongly connected component may be less resilient to random damage than the giant weakly connected one.
引用
收藏
页数:4
相关论文
共 19 条
[1]   Topology of evolving networks:: Local events and universality [J].
Albert, R ;
Barabási, AL .
PHYSICAL REVIEW LETTERS, 2000, 85 (24) :5234-5237
[2]   Internet -: Diameter of the World-Wide Web [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 1999, 401 (6749) :130-131
[3]   Error and attack tolerance of complex networks [J].
Albert, R ;
Jeong, H ;
Barabási, AL .
NATURE, 2000, 406 (6794) :378-382
[4]   Emergence of scaling in random networks [J].
Barabási, AL ;
Albert, R .
SCIENCE, 1999, 286 (5439) :509-512
[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]   Network robustness and fragility: Percolation on random graphs [J].
Callaway, DS ;
Newman, MEJ ;
Strogatz, SH ;
Watts, DJ .
PHYSICAL REVIEW LETTERS, 2000, 85 (25) :5468-5471
[7]   Resilience of the Internet to random breakdowns [J].
Cohen, R ;
Erez, K ;
ben-Avraham, D ;
Havlin, S .
PHYSICAL REVIEW LETTERS, 2000, 85 (21) :4626-4628
[8]   Structure of growing networks with preferential linking [J].
Dorogovtsev, SN ;
Mendes, JFF ;
Samukhin, AN .
PHYSICAL REVIEW LETTERS, 2000, 85 (21) :4633-4636
[9]  
Dorogovtsev SN, 2001, PHYS REV E, V63, DOI [10.1103/PhysRevE.63.056125, 10.1103/PhysRevE.63.062101]
[10]  
DOROGOVTSEV SN, CONDMAT0012009