Critical dynamics of the k-core pruning process

Abstract

We present the theory of the k-core pruning process (progressive removal of nodes with degree less than k) in uncorrelated random networks. We derive exact equations describing this process and the evolution of the network structure, and solve them numerically and, in the critical regime of the process, analytically. We show that the pruning process exhibits three different behaviors depending on whether the mean degree <q> of the initial network is above, equal to, or below the threshold <q>_c corresponding to the emergence of the giant k-core. We find that above the threshold the network relaxes exponentially to the k-core. The system manifests the phenomenon known as "critical slowing down", as the relaxation time diverges when <q> tends to <q>_c. At the threshold, the dynamics become critical characterized by a power-law relaxation (1/t^2). Below the threshold, a long-lasting transient process (a "plateau" stage) occurs. This transient process ends with a collapse in which the entire network disappears completely. The duration of the process diverges when <q> tends to <q>_c. We show that the critical dynamics of the pruning are determined by branching processes of spreading damage. Clusters of nodes of degree exactly k are the evolving substrate for these branching processes. Our theory completely describes this branching cascade of damage in uncorrelated networks by providing the time dependent distribution function of branching. These theoretical results are supported by our simulations of the $k$-core pruning in Erdos-Renyi graphs.

12 pages, 10 figures

References in corpus (5)

• The structure and dynamics of multilayer networks
• Critical phenomena in complex networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Dynamics of k-core percolation in a random graph

Cited by in corpus (36)

• Hybrid Phase Transition into an Absorbing State: Percolation and Avalanches
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Epidemics, the Ising-model and percolation theory: a comprehensive review focussed on Covid-19
• Equivalence of several generalized percolation models on networks
• Interevent time distribution, burst, and hybrid percolation transition
• Targeted Damage to Interdependent Networks
• Effective potential approach to hybrid synchronization transitions
• Diverse types of percolation transitions
• Structural stability of interaction networks against negative external fields
• Critical behavior of $k$-core percolation: Numerical studies
• Relevance of backtracking paths in epidemic spreading on networks
• The fate of the bootstrap percolation hybrid critical point in finite dimension
• Scaling and universality in glass transition
• $(k,q)$-core decomposition of hypergraphs
• Prediction and mitigation of nonlocal cascading failures using graph neural networks
• Metastable state en route to traveling-wave synchronization state
• Failure-recovery model with competition between failures in complex networks: a dynamical approach
• Critical behavior of a two-step contagion model with multiple seeds
• Unified framework for hybrid percolation transitions based on microscopic dynamics
• Impact of Committed Minorities: Unveiling Critical Mass of Cooperation in the Iterated Prisoner's Dilemma Game
• Convexity in complex networks
• Critical phenomena of a hybrid phase transition in cluster merging dynamics
• Random node reinforcement and $K$-core structure of complex networks
• Two golden times in two-step contagion models
• Two faces of greedy leaf removal procedure on graphs
• Hierarchical cycle-tree packing model for $K$-core attack problem
• Weak percolation on multiplex networks with overlapping edges
• Generalized $k$-core pruning process on directed networks
• Hysteresis and criticality in hybrid percolation transitions
• Vulnerability and Resilience of Social Engagement: Equilibrium Theory
• Link rewiring with local information--induced hybrid percolation transitions
• Cooperation transitions in social games induced by aspiration-driven players
• Discontinuous transition in explosive percolation via local suppression
• Non-equilibrium phase transition and cultural drift in the continuous-trait Axelrod model
• Discontinuous percolation via suppression of neighboring clusters in a network
• Anomalous percolation transitions beyond the BKT transition in growing networks