Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks

Abstract

We introduce the heterogeneous-$k$-core, which generalizes the $k$-core, and contrast it with bootstrap percolation. Vertices have a threshold $k_i$ which may be different at each vertex. If a vertex has less than $k_i$ neighbors it is pruned from the network. The heterogeneous-$k$-core is the sub-graph remaining after no further vertices can be pruned. If the thresholds $k_i$ are $1$ with probability $f$ or $k\ge 3$ with probability $(1-f)$, the process forms one branch of an activation-pruning process which demonstrates hysteresis. The other branch is formed by ordinary bootstrap percolation. We show that there are two types of transitions in this heterogeneous-$k$-core process: the giant heterogeneous-$k$-core may appear with a continuous transition and there may be a second, discontinuous, hybrid transition. We compare critical phenomena, critical clusters and avalanches at the heterogeneous-$k$-core and bootstrap percolation transitions. We also show that network structure has a crucial effect on these processes, with the giant heterogeneous-$k$-core appearing immediately at a finite value for any $f>0$ when the degree distribution tends to a power law $P(q)\sim q^{-\gamma }$ with $\gamma <3$.

10 pages, 4 figures

References in corpus (28)

• Statistical mechanics of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• MEDUSA - New Model of Internet Topology Using k-shell Decomposition
• k-core organization of complex networks
• Percolation Critical Exponents in Scale-Free Networks
• Thermodynamic limit of the first-order phase transition in the Kuramoto model
• Bootstrap Percolation on Complex Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Jamming Percolation and Glass Transitions in Lattice Models
• How clustering affects the bond percolation threshold in complex networks
• The Physics of Living Neural Networks
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• The k-core and branching processes
• Hysteresis in the Random Field Ising Model and Bootstrap Percolation
• Stochastic cellular automata model of neural networks
• Rhythmogenic neuronal networks, pacemakers, and k-cores
• Analytical results for bond percolation and k-core sizes on clustered networks
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• On $k$-Core Percolation in Four Dimensions
• Rigidity percolation in a field
• Dynamics of k-core percolation in a random graph
• Dynamics of k-core percolation
• Nested Subgraphs of Complex Networks
• Dynamics of bootstrap percolation

Cited by in corpus (55)

• The Kuramoto model in complex networks
• Avalanche Collapse of Interdependent Network
• Percolation on complex networks: Theory and application
• Percolation in Multiplex Networks with Overlap
• Towards real-world complexity: an introduction to multiplex networks
• Kuramoto model with frequency-degree correlations on complex networks
• Cascading Failures in Complex Networks
• k-Core percolation on multiplex networks
• Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
• How does public opinion become extreme?
• Weak percolation on multiplex networks
• Dynamics of social contagions with heterogeneous adoption thresholds: Crossover phenomena in phase transition
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Cascading Failures in Interdependent Networks with Multiple Supply-Demand Links and Functionality Thresholds
• Competing contagion processes: Complex contagion triggered by simple contagion
• Tricritical point in heterogeneous k-core percolation
• Equivalence of several generalized percolation models on networks
• Social contagions with communication channels alternation on multiplex networks
• Targeted Damage to Interdependent Networks
• Critical phenomena in heterogeneous k-core percolation
• Cascading failures in interdependent networks with finite functional components
• Structural stability of interaction networks against negative external fields
• Network Overload due to Massive Attacks
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Scaling and universality in glass transition
• $(k,q)$-core decomposition of hypergraphs
• Generalized model for $k$-core percolation and interdependent networks
• Reversible bootstrap percolation: Fake news and fact checking
• Mixed-order phase transition of the contact process near multiple junctions
• Insights into bootstrap percolation: Its equivalence with k-core percolation and the giant component
• A unified approach to percolation processes on multiplex networks
• Epidemic control in networks with cliques
• Core organization of directed complex networks
• A trust model for spreading gossip in social networks
• Distribution of blackouts in the power grid and the Motter and Lai model
• Influence Maximization for Fixed Heterogeneous Thresholds
• Interdependent transport via percolation backbones in spatial networks
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• Sudden spreading of infections in an epidemic model with a finite seed fraction
• Universality of critically pinned interfaces in 2-dimensional isotropic random media
• Critical phenomena on k-booklets
• Random node reinforcement and $K$-core structure of complex networks
• Enhanced robustness of single-layer networks with redundant dependencies
• Weak percolation on multiplex networks with overlapping edges
• Percolation in Media with Columnar Disorder
• Double transitions and hysteresis in heterogeneous contagion processes
• Role of hubs in the synergistic spread of behavior
• Cluster structure and dynamics in gels and glasses
• Emergent networks in fractional percolation
• Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
• Selective Bootstrap Percolation
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Weak Multiplex Percolation
• Large Social Networks can be Targeted for Viral Marketing with Small Seed Sets
• Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics