Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
arXiv:2009.04249 · doi:10.1103/PhysRevE.101.062308
Abstract
We present analytical results for the structural evolution of random networks undergoing contraction processes via generic node deletion scenarios, namely, random deletion, preferential deletion and propagating deletion. Focusing on configuration model networks, which exhibit a given degree distribution and no correlations, we show using a rigorous argument that upon contraction the degree distributions of these networks converge towards a Poisson distribution. To this end, we use the relative entropy of the degree distribution of the contracting network at time with respect to the corresponding Poisson distribution with the same mean degree as a distance measure between and Poisson. The relative entropy is suitable as a distance measure since it satisfies for any degree distribution , while equality is obtained only for . We derive an equation for the time derivative during network contraction and show that the relative entropy decreases monotonically to zero during the contraction process. We thus conclude that the degree distributions of contracting configuration model networks converge towards a Poisson distribution. Since the contracting networks remain uncorrelated, this means that their structures converge towards an Erd{\H o}s-Rényi (ER) graph structure, substantiating earlier results obtained using direct integration of the master equation and computer simulations [I. Tishby, O. Biham and E. Katzav, {\it Phys. Rev. E} {\bf 100}, 032314 (2019)]. We demonstrate the convergence for configuration model networks with degenerate degree distributions (random regular graphs), exponential degree distributions and power-law degree distributions (scale-free networks).
arXiv comment41 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:2009.02890
References in corpus (23)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Epidemic spreading in scale-free networks
- The diameter of the world wide web
- Epidemic processes in complex networks
- Random graphs with arbitrary degree distributions and their applications
- 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
- Immunization of complex networks
- Connectivity of Growing Random Networks
- Network dismantling
- Dynamically induced cascading failures in power grids
- The entropy of network ensembles
- The entropy of randomized network ensembles
- Fast and simple decycling and dismantling of networks
- Homogeneous complex networks
- 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
- Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
Cited by in corpus (6)
- The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
- The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
- Phase transition in evolving networks that combine preferential attachment and random node deletion
- 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