Bootstrap Percolation on Complex Networks

Abstract

We consider bootstrap percolation on uncorrelated complex networks. We obtain the phase diagram for this process with respect to two parameters: $f$, the fraction of vertices initially activated, and $p$, the fraction of undamaged vertices in the graph. We observe two transitions: the giant active component appears continuously at a first threshold. There may also be a second, discontinuous, hybrid transition at a higher threshold. Avalanches of activations increase in size as this second critical point is approached, finally diverging at this threshold. We describe the existence of a special critical point at which this second transition first appears. In networks with degree distributions whose second moment diverges (but whose first moment does not), we find a qualitatively different behavior. In this case the giant active component appears for any $f>0$ and $p>0$, and the discontinuous transition is absent. This means that the giant active component is robust to damage, and also is very easily activated. We also formulate a generalized bootstrap process in which each vertex can have an arbitrary threshold.

9 pages, 3 figures

References in corpus (3)

• Critical phenomena in complex networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• The Physics of Living Neural Networks

Cited by in corpus (75)

• Robustness and resilience of complex networks
• Recent advances in percolation theory and its applications
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Percolation on complex networks: Theory and application
• High-accuracy approximation of binary-state dynamics on networks
• Multiplexity-facilitated cascades in networks
• Percolation in Interdependent and Interconnected Networks: Abrupt Change from Second to First Order Transition
• Statistical physics approaches to the complex Earth system
• Towards real-world complexity: an introduction to multiplex networks
• Percolation of Partially Interdependent Scale-free Networks
• Dynamics of social contagions with memory of non-redundant information
• Cascading Failures in Complex Networks
• Eradicating Catastrophic Collapse in Interdependent Networks via Reinforced Nodes
• Cascades on a class of clustered random networks
• Message passing theory for percolation models on multiplex networks with link overlap
• Local structure can identify and quantify influential global spreaders in large scale social networks
• How does public opinion become extreme?
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Weak percolation on multiplex networks
• Inducing Effect on the Percolation Transition in Complex Networks
• Multiple resource demands and viability in multiplex networks
• From the origin of life to pandemics: Emergent phenomena in complex systems
• Coupled catastrophes: sudden shifts cascade and hop among interdependent systems
• Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds
• Competing contagion processes: Complex contagion triggered by simple contagion
• The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
• Efficient collective influence maximization in cascading processes with first-order transitions
• Non-consensus opinion models on complex networks
• A message-passing approach for threshold models of behavior in networks
• Explosive spreading on complex networks: the role of synergy
• Equivalence of several generalized percolation models on networks
• Social contagions with communication channels alternation on multiplex networks
• Structural stability of interaction networks against negative external fields
• Cascading failures in interdependent networks with finite functional components
• Synergistic interactions promote behavior spreading and alter phase transition on multiplex networks
• Network Overload due to Massive Attacks
• Network Properties for Robust Multilayer Infrastructure Systems: A Percolation Theory Review
• Self-Organization of Dragon Kings
• Cooperative heterogeneous facilitation: multiple glassy states and glass-glass transition
• Generalized model for $k$-core percolation and interdependent networks
• Reversible bootstrap percolation: Fake news and fact checking
• Bootstrap percolation on geometric inhomogeneous random graphs
• Phase Transitions in the Quadratic Contact Process on Complex Networks
• Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
• A unified approach to percolation processes on multiplex networks
• Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
• Newman-Ziff algorithm for the bootstrap percolation: application to the Archimedean lattices
• Microscopic models of mode-coupling theory: the $F_{12}$ scenario
• Disconnected glass-glass transitions and swallowtail bifurcations in microscopic spin models with facilitated dynamics
• A trust model for spreading gossip in social networks
• Distribution of blackouts in the power grid and the Motter and Lai model
• Extended-range percolation in complex networks
• Influence Maximization for Fixed Heterogeneous Thresholds
• Systems poised to criticality through Pareto selective forces
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Bifurcations in synergistic epidemics on random regular graphs
• Bootstrap and diffusion percolation transitions in three-dimensional lattices
• The large connectivity limit of bootstrap percolation
• Double transitions and hysteresis in heterogeneous contagion processes
• No-exclaves percolation on random networks
• A sharper threshold for bootstrap percolation in two dimensions
• Competing contact processes on homogeneous networks with tunable clusterization
• Selective Bootstrap Percolation
• Structure and Stability of the Indian Power Transmission Network
• Induced Percolation on Networked Systems
• Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption
• Emergent networks in fractional percolation
• Discontinuous percolation via suppression of neighboring clusters in a network
• The Routing of Complex Contagion in Kleinberg's Small-World Networks
• Color-avoiding percolation in edge-colored Erdős-Rényi graphs
• Thermodynamic analysis of diverse percolation transitions
• Bond percolation in distorted simple cubic and body-centered cubic lattices
• Incentivized Campaigning in Social Networks
• Phase transition in the diffusion and bootstrap percolation models on regular random and Erdős-Rényi networks