Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes

Abstract

In a highly influential paper twenty years ago, Barabási and Albert [Science 286, 509 (1999)] showed that networks undergoing generic growth processes with preferential attachment evolve towards scale-free structures. In any finite system, the growth eventually stalls and is likely to be followed by a phase of network contraction due to node failures, attacks or epidemics. Using the master equation formulation and computer simulations we analyze the structural evolution of networks subjected to contraction processes via random, preferential and propagating node deletions. We show that the contracting networks converge towards an Erd{\H o}s-Rényi network structure whose mean degree continues to decrease as the contraction proceeds. This is manifested by the convergence of the degree distribution towards a Poisson distribution and the loss of degree-degree correlations.

arXiv comment30 pages, 5 figures, supplemental material and movie. To view supplemental files, please download and extract the gzipped tar source file listed under "Other formats"

References in corpus (22)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Catastrophic cascade of failures in interdependent networks
• The diameter of the world wide web
• Epidemic processes in complex networks
• Mixing patterns in networks
• Resilience of the Internet to random breakdowns
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• A model for cascading failures in complex networks
• Network dismantling
• Dynamically induced cascading failures in power grids
• Homogeneous complex networks
• Degree Correlation in Scale-Free Graphs
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Cascading collapse of online social networks
• Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
• Maximal entropy random networks with given degree distribution

Cited by in corpus (7)

• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Phase transition in evolving networks that combine preferential attachment and random node deletion
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Degree distributions under general node removal: Power-law or Poisson?
• Ensemble inequivalence and phase transitions in unlabeled networks
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment