Abstract
We present the theory of the -core pruning process (progressive removal of nodes with degree less than ) 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 of the initial network is above, equal to, or below the threshold corresponding to the emergence of the giant -core. We find that above the threshold the network relaxes exponentially to the -core. The system manifests the phenomenon known as “critical slowing-down,” as the relaxation time diverges when tends to . At the threshold, the dynamics become critical, characterized by a power-law relaxation (). 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 . We show that the critical dynamics of the pruning are determined by branching processes of spreading damage. Clusters of nodes of degree exactly 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 -core pruning in Erdős-Rényi graphs.
3 More- Received 20 May 2015
DOI:https://doi.org/10.1103/PhysRevX.5.031017
This article is available under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Popular Summary
If the nodes in a network depend on the support of their neighbors to survive or function, small perturbations can cause the system to suddenly collapse. Such is the case in financial systems, interdependent infrastructure, and brain activity. A model capturing this behavior is the -core, in which each node’s number of neighbors (degree) must be at least . In the -core pruning process, nodes that have a degree less than are removed at each time step. The pruning repeats until either the network is destroyed completely or a stable -core (i.e., the densest part of the network) emerges. We propose a simple theoretical method that allows for the exact calculation of the evolution of the system in order to understand these phenomena.
We conduct numerical and analytical analyses of sparse random networks. As the system approaches the critical threshold (i.e., the point at which one single -core remains), it undergoes “critical slowing down”; the pruning process lasts longer and longer as the system approaches the collapse threshold. Our method yields exact equations for the evolution of the degree distribution in uncorrelated random networks, and we find that the pruning process occurs in one of three regimes. Below the critical threshold, the system collapses in a time that grows as the inverse square root of the distance from the threshold. Above the threshold, the system relaxes exponentially to a stable state, and the relaxation time similarly diverges. Exactly at the threshold, the dynamics exhibit a power-law relaxation typical of critical states. We explain these phenomena as a branching process as damage (pruning) spreads from node to node in independent branching trees.
Our results for the -core pruning process and accompanying structural changes can shed light on similar collective phenomena that occur in many other complex systems such as mass extinctions and the spread of contagious diseases.