Phase transition in evolving networks that combine preferential attachment and random node deletion

Abstract

Analytical results are presented for the structure of networks that evolve via a preferential-attachment-random-deletion (PARD) model in the regime of overall network growth and in the regime of overall contraction. The phase transition between the two regimes is studied. At each time step a node addition and preferential attachment step takes place with probability $P_{\mathrm{add}}$, and a random node deletion step takes place with probability $P_{\mathrm{del}}=1-P_{\mathrm{add}}$. The balance between growth and contraction is captured by the parameter $\eta =P_{\mathrm{add}}-P_{\mathrm{del}}$, which in the regime of overall network growth satisfies $0<\eta \le 1$ and in the regime of overall network contraction $-1\le \eta <0$. Using the master equation and computer simulations we show that for $-1<\eta <0$ the time-dependent degree distribution $P_t(k)$ converges towards a stationary form $P_{\mathrm{st}}(k)$ which exhibits an exponential tail. This is in contrast with the power-law tail of the stationary degree distribution obtained for $0<\eta \le 1$. Thus, the PARD model has a phase transition at $\eta =0$, which separates between two structurally distinct phases. At the transition, for $\eta =0$, the degree distribution exhibits a stretched exponential tail. While the stationary degree distribution in the phase of overall growth represents an asymptotic state, in the phase of overall contraction $P_{\mathrm{st}}(k)$ represents an intermediate asymptotic state of a finite life span, which disappears when the network vanishes.

32 pages, 6 figures. arXiv admin note: text overlap with arXiv:2209.10027

References in corpus (17)

• Statistical mechanics of complex networks
• Network dismantling
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Percolation of localized attack on complex networks
• Fast and simple decycling and dismantling of networks
• The influence of the broadness of the degree distribution on network's robustness: comparing localized attack and random attack
• $k$-core percolation on complex networks: Comparing random, localized and targeted attacks
• Resilience of Networks Formed of Interdependent Modular Networks
• Spreading of localized attacks in spatial multiplex networks
• Cascading collapse of online social networks
• Topological phase transition in a network model with preferential attachment and node removal
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• The nature of the long time decay at a second order transition point
• Stochastic resetting in a networked multiparticle system with correlated transitions
• The Fokker-Planck operator at a continuous phase transition

Cited by in corpus (1)

• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment