• Open Access

Critical Dynamics of the k-Core Pruning Process

G. J. Baxter, S. N. Dorogovtsev, K.-E. Lee, J. F. F. Mendes, and A. V. Goltsev
Phys. Rev. X 5, 031017 – Published 18 August 2015

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 qc 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 qc. At the threshold, the dynamics become critical, characterized by a power-law relaxation (1/t2). 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 qqc. 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 Erdős-Rényi graphs.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
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

Authors & Affiliations

G. J. Baxter1, S. N. Dorogovtsev1,2, K.-E. Lee1, J. F. F. Mendes1, and A. V. Goltsev1,2,*

  • 1Department of Physics and I3N, University of Aveiro, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal
  • 2A.F. Ioffe Physico-Technical Institute, 194021 St. Petersburg, Russia

  • *goltsev@ua.pt

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 k-core, in which each node’s number of neighbors (degree) must be at least k. In the k-core pruning process, nodes that have a degree less than k are removed at each time step. The pruning repeats until either the network is destroyed completely or a stable k-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 k-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 k-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.

Key Image

Article Text

Click to Expand

References

Click to Expand
Issue

Vol. 5, Iss. 3 — July - September 2015

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 3.0 License. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×