Giant strongly connected component of directed networks
arXiv:cond-mat/0103629 · doi:10.1103/PhysRevE.64.025101
Abstract
We describe how to calculate the sizes of all giant connected components of a directed graph, including the {\em strongly} connected one. Just to the class of directed networks, in particular, belongs the World Wide Web. The results are obtained for graphs with statistically uncorrelated vertices and an arbitrary joint in,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.
4 pages revtex, 4 figures
References in corpus (2)
Cited by in corpus (89)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Epidemic processes in complex networks
- The spread of epidemic disease on networks
- Evolution of networks
- Critical phenomena in complex networks
- The network of global corporate control
- Understanding the spreading patterns of mobile phone viruses
- Percolation on complex networks: Theory and application
- Second look at the spread of epidemics on networks
- Network Geometry
- Percolation in Directed Scale-Free Networks
- k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
- Analysis of complex contagions in random multiplex networks
- On the Origins of Hierarchy in Complex Networks
- Generalized percolation in random directed networks
- Disease spread through animal movements: a static and temporal network analysis of pig trade in Germany
- Anomalous percolating properties of growing networks
- Components in time-varying graphs
- Random graph models for directed acyclic networks
- Group percolation in interdependent networks
- Network-based analysis of stochastic SIR epidemic models with random and proportionate mixing
- Spectral Theory of Sparse Non-Hermitian Random Matrices
- Thesaurus as a complex network
- Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
- Early fragmentation in the adaptive voter model on directed networks
- Empirical analysis of the ship-transport network of China
- Using graph concepts to understand the organization of complex systems
- Emergence of the giant weak-component in directed random graphs with arbitrary degree distributions
- Giant components in directed multiplex networks
- Network structural origin of instabilities in large complex systems
- Escaping from cycles through a glass transition
- Effect of node deleting on network structure
- Sensitivity of directed networks to the addition and pruning of edges and vertices
- Probabilistic heuristics for disseminating information in networks
- Linear stability analysis for large dynamical systems on directed random graphs
- Localization and universality of eigenvectors in directed random graphs
- Universal transient behavior in large dynamical systems on networks
- Conservation laws for voter-like models on directed networks
- Interfaces and the edge percolation map of random directed networks
- Network Properties for Robust Multilayer Infrastructure Systems: A Percolation Theory Review
- Sampling properties of directed networks
- Boolean delay equations on networks: An application to economic damage propagation
- Input graph: the hidden geometry in controlling complex networks
- Dynamical systems on large networks with predator-prey interactions are stable and exhibit oscillations
- Percolation on Isotropically Directed Lattice
- Phase transitions in Ising models on directed networks
- Supremacy distribution in evolving networks
- Hierarchy in directed random networks
- From one-way streets to percolation on random mixed graphs
- Non-normality and non-monotonic dynamics in complex reaction networks
- Effects of Preference for Attachment to Low-degree Nodes on the Degree Distributions of a Growing Directed Network and a Simple Food-Web Model
- Determining the Solution Space of Vertex-Cover by Interactions and Backbones
- The distribution of first hitting times of random walks on directed Erdős-Rényi networks
- Kauffman Boolean model in undirected scale free networks
- Agreement dynamics on directed random graphs
- Structural efficiency of percolation landscapes in flow networks
- Inhomogeneous percolation models for spreading phenomena in random graphs
- Network algorithmics and the emergence of information integration in cortical models
- Generalized -core pruning process on directed networks
- Network algorithmics and the emergence of the cortical synaptic-weight distribution
- Detecting and modelling real percolation and phase transitions of information on social media
- Feedback arcs and node hierarchy in directed networks
- Robustness and Directed Structures in Ecological Flow Networks
- New generation of mobile phone viruses and corresponding countermeasures
- Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
- The Atlas for the Aspiring Network Scientist
- Organisation of signal flow in directed networks
- The network structure of mathematical knowledge according to the Wikipedia, MathWorld, and DLMF online libraries
- Critical line in undirected Kauffman boolean networks - the role of percolation
- Connected components in networks with higher-order interactions
- Prisoner's dilemma on directed networks
- Janus Percolation in Anisotropic Limited-Degree Networks
- Growing Network Models Having Part Edges Removed/added Randomly
- Bipartitioning of directed and mixed random graphs
- On the Role of Triadic Substructures in Complex Networks
- Optimal Disruption of Complex Networks
- Are giants in random digraphs `almost' local?
- Topological Components in a Community Currency Network
- Network algorithmics and the emergence of synchronization in cortical models
- Mean-field approximation and phase transitions in an Ising-voter model on directed regular random graphs
- Achieving Small World Properties using Bio-Inspired Techniques in Wireless Networks
- Reachability and recoverability of sink nodes in growing acyclic directed networks
- Nonreciprocal random networks and their percolation properties
- Correspondent Banking Networks: Theory and Experiment
- Network Horizon Dynamics I: Qualitative Aspects
- The strong giant in a random digraph
- Gracefully Degrading Consensus and -Set Agreement in Directed Dynamic Networks
- Understanding following patterns among high-performance athletes