k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects

Abstract

We develop the theory of the k-core (bootstrap) percolation on uncorrelated random networks with arbitrary degree distributions. We show that the k-core percolation is an unusual, hybrid phase transition with a jump emergence of the k-core as at a first order phase transition but also with a critical singularity as at a continuous transition. We describe the properties of the k-core, explain the meaning of the order parameter for the k-core percolation, and reveal the origin of the specific critical phenomena. We demonstrate that a so-called ``corona'' of the k-core plays a crucial role (corona is a subset of vertices in the k-core which have exactly k neighbors in the k-core). It turns out that the k-core percolation threshold is at the same time the percolation threshold of finite corona clusters. The mean separation of vertices in corona clusters plays the role of the correlation length and diverges at the critical point. We show that a random removal of even one vertex from the k-core may result in the collapse of a vast region of the k-core around the removed vertex. The mean size of this region diverges at the critical point. We find an exact mapping of the k-core percolation to a model of cooperative relaxation. This model undergoes critical relaxation with a divergent rate at some critical moment.

11 pages, 8 figures

References in corpus (15)

• Error and attack tolerance of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• k-core organization of complex networks
• Random Packings of Frictionless Particles
• Clique percolation in random networks
• Percolation Critical Exponents in Scale-Free Networks
• Giant strongly connected component of directed networks
• Multiscaling at Point J: Jamming is a Critical Phenomenon
• Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics
• Metric structure of random networks
• First-order rigidity transition on Bethe Lattices
• Multiphase Superconductivity in Skutterudite PrOs_4Sb_12

Cited by in corpus (93)

• Characterization of complex networks: A survey of measurements
• Critical phenomena in complex networks
• The Kuramoto model 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 on complex networks: Theory and application
• Characterizing the dynamical importance of network nodes and links
• High-accuracy approximation of binary-state dynamics on networks
• Bootstrap Percolation on Complex Networks
• Recent advances and open challenges in percolation
• Kuramoto model with frequency-degree correlations on complex networks
• Resilience and rewiring of the passenger airline networks in the United States
• Core percolation on complex networks
• Cascades on a class of clustered random networks
• k-Core percolation on multiplex networks
• Higher-order percolation processes on multiplex hypergraphs
• How does public opinion become extreme?
• Heterogeneous-k-core versus Bootstrap Percolation on Complex Networks
• A Clarified Typology of Core-Periphery Structure in Networks
• Recent advances of percolation theory in complex networks
• Outbreaks of coinfections: the critical role of cooperativity
• From the origin of life to pandemics: Emergent phenomena in complex systems
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Percolation transition in networks with degree-degree correlation
• Competing contagion processes: Complex contagion triggered by simple contagion
• Tricritical point in heterogeneous k-core percolation
• Efficient collective influence maximization in cascading processes with first-order transitions
• On Bootstrap Percolation in Living Neural Networks
• Critical dynamics of the k-core pruning process
• Organization of modular networks
• An In-Depth Analysis of Stochastic Kronecker Graphs
• Phase Transitions in Cooperative Coinfections: Simulation Results for Networks and Lattices
• Stochastic cellular automata model of neural networks
• Fluctuations in percolation of sparse complex networks
• Message-passing theory for cooperative epidemics
• Equivalence of several generalized percolation models on networks
• Giant components in directed multiplex networks
• Mutually cooperative epidemics on power-law networks
• Effective potential approach to hybrid synchronization transitions
• First-order phase transitions in outbreaks of co-infectious diseases and the extended general epidemic process
• Diverse types of percolation transitions
• Critical phenomena in heterogeneous k-core percolation
• Structural stability of interaction networks against negative external fields
• Critical behavior of $k$-core percolation: Numerical studies
• Analytical results for bond percolation and k-core sizes on clustered networks
• Critical phenomena and noise-induced phase transitions in neuronal networks
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Percolation-induced PT symmetry breaking
• Cascading collapse of online social networks
• The nature of hypergraph $k$-core percolation problems
• Cascades on clique-based graphs
• The fate of the bootstrap percolation hybrid critical point in finite dimension
• Interconnections between networks act like an external field in first-order percolation transitions
• Topological structure and the H-index in complex networks
• k-core percolation on interdependent and interconnected multiplex networks
• Scaling and universality in glass transition
• $(k,q)$-core decomposition of hypergraphs
• Mixed-order phase transition of the contact process near multiple junctions
• Prediction and mitigation of nonlocal cascading failures using graph neural networks
• On $k$-Core Percolation in Four Dimensions
• Color-avoiding percolation
• Stylized facts in Brazilian vote distributions
• Cascades in real interbank markets
• Dynamics of k-core percolation in a random graph
• Exact solution of generalized cooperative SIR dynamics
• Optimal redundancy against disjoint vulnerabilities in networks
• Dynamics of k-core percolation
• Bond and site color-avoiding percolation in scale free networks
• Exotic phase transitions of k-cores in clustered networks
• The dynamical collision network in granular gases
• Nested Subgraphs of Complex Networks
• Critical phenomena of a hybrid phase transition in cluster merging dynamics
• Effect of network clustering on mutually cooperative coinfections
• Efficient Core Maintenance in Large Dynamic Graphs
• Critical phenomena on k-booklets
• Two golden times in two-step contagion models
• Percolation in Media with Columnar Disorder
• Phase transitions on a class of generalized Vicsek-like models of collective motion
• Emergence of biconnected clusters in explosive percolation
• The large connectivity limit of bootstrap percolation
• Perturb and Combine to Identify Influential Spreaders in Real-World Networks
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• The Atlas for the Aspiring Network Scientist
• Quantum $k$-core conduction on the Bethe lattice
• COREATTACK: Breaking Up the Core Structure of Graphs
• Complex Contagions and hybrid phase transitions in unclustered and clustered random networks
• Analytical approach to the dynamics of facilitated spin models on random networks
• Universality in percolation of arbitrary Uncorrelated Nested Subgraphs
• Level statistics for quantum $k$-core percolation
• Mixing time of a kinetically constrained spin model on trees: power law scaling at criticality
• Computation of K-Core Decomposition on Giraph
• Effect of money heterogeneity on resource dependency in complex networks