Giant strongly connected component of directed networks
- 19 July 2001
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 64 (2) , 025101
- https://doi.org/10.1103/physreve.64.025101
Abstract
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 We show that if 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.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Degree Distributions of Growing NetworksPhysical Review Letters, 2001
- Scaling properties of scale-free evolving networks: Continuous approachPhysical Review E, 2001
- Dynamics of directed graphs: the world-wide WebPhysica A: Statistical Mechanics and its Applications, 2001
- Network Robustness and Fragility: Percolation on Random GraphsPhysical Review Letters, 2000
- Topology of Evolving Networks: Local Events and UniversalityPhysical Review Letters, 2000
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- Structure of Growing Networks with Preferential LinkingPhysical Review Letters, 2000
- Error and attack tolerance of complex networksNature, 2000
- Emergence of Scaling in Random NetworksScience, 1999
- Diameter of the World-Wide WebNature, 1999