Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component

Abstract

K-core and bootstrap percolation are widely studied models that have been used to represent and understand diverse deactivation and activation processes in natural and social systems. Since these models are considerably similar, it has been suggested in recent years that they could be complementary. In this manuscript we provide a rigorous analysis that shows that for any degree and threshold distributions heterogeneous bootstrap percolation can be mapped into heterogeneous k-core percolation and vice versa, if the functionality thresholds in both processes satisfy a complementary relation. Another interesting problem in bootstrap and k-core percolation is the fraction of nodes belonging to their giant connected components $P_{\infty b}$ and $P_{\infty c}$, respectively. We solve this problem analytically for arbitrary randomly connected graphs and arbitrary threshold distributions, and we show that $P_{\infty b}$ and $P_{\infty c}$ are not complementary. Our theoretical results coincide with computer simulations in the limit of very large graphs. In bootstrap percolation, we show that when using the branching theory to compute the size of the giant component, we must consider two different types of links, which are related to distinct spanning branches of active nodes.

References in corpus (18)

• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• k-core organization of complex networks
• Evidence of Complex Contagion of Information in Social Media: An Experiment Using Twitter Bots
• Bootstrap Percolation on Complex Networks
• Systemic Risk in a Unifying Framework for Cascading Processes on Networks
• Threshold cascades with response heterogeneity in multiplex networks
• Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• Dynamics of social contagions with heterogeneous adoption thresholds: Crossover phenomena in phase transition
• Optimal Path and Minimal Spanning Trees in Random Weighted Networks
• Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds
• Tricritical point in heterogeneous k-core percolation
• Equivalence of several generalized percolation models on networks
• Generalized epidemic process on modular networks
• Critical phenomena in heterogeneous k-core percolation

Cited by in corpus (7)

• Percolation on complex networks: Theory and application
• Cascading Failures in Complex Networks
• Universal behavior of site and bond percolation thresholds on regular lattices with compact extended-range neighborhoods in 2 and 3 dimensions
• Reversible bootstrap percolation: Fake news and fact checking
• Epidemic control in networks with cliques
• A trust model for spreading gossip in social networks
• Extended-range percolation in five dimensions