Exhaustive percolation on random networks

Abstract

We consider propagation models that describe the spreading of an attribute, called "damage", through the nodes of a random network. In some systems, the average fraction of nodes that remain undamaged vanishes in the large system limit, a phenomenon we refer to as exhaustive percolation. We derive scaling law exponents and exact results for the distribution of the number of undamaged nodes, valid for a broad class of random networks at the exhaustive percolation transition and in the exhaustive percolation regime. This class includes processes that determine the set of frozen nodes in random Boolean networks with indegree distributions that decay sufficiently rapidly with the number of inputs. Connections between our calculational methods and previous studies of percolation beginning from a single initial node are also pointed out. Central to our approach is the observation that key aspects of damage spreading on a random network are fully characterized by a single function specifying the probability that a given node will be damaged as a function of the fraction of damaged nodes. In addition to our analytical investigations of random networks, we present a numerical example of exhaustive percolation on a directed lattice.

19 pages, 7 figures; corrected errors in eq. (73) and some typos

References in corpus (15)

• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• Efficient Immunization Strategies for Computer Networks and Populations
• A model for cascading failures in complex networks
• Cascade control and defense in complex networks
• Modeling Cascading Failures in the North American Power Grid
• Genetic networks with canalyzing Boolean rules are always stable
• Instability of scale-free networks under node-breaking avalanches
• Scaling in ordered and critical random Boolean networks
• Stability of the Kauffman Model
• Relevant elments, Magnetization and Dynamical Properties in Kauffman Networks: a Numerical Study
• On the number of attractors in random Boolean networks
• Scaling in critical random Boolean networks

Cited by in corpus (15)

• Percolation on complex networks: Theory and application
• Mutual information in random Boolean models of regulatory networks
• Statistical Properties of Avalanches in Networks
• The interdependent network of gene regulation and metabolism is robust where it needs to be
• Damage Spreading and Criticality in Finite Random Dynamical Networks
• Attractors in continuous and Boolean networks
• Dynamical Instability in Boolean Networks as a Percolation Problem
• Broad edge of chaos in strongly heterogeneous Boolean networks
• On irreversible dynamic monopolies in general graphs
• Boolean modeling of collective effects in complex networks
• Quantifying the complexity of random Boolean networks
• Symmetry in Critical Random Boolean Network Dynamics
• Formation of the frozen core in critical Boolean Networks
• Random logic networks: from classical Boolean to quantum dynamics
• When correlations matter - response of dynamical networks to small perturbations