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 $\hat{I}\cdot =P_{\mathrm{add}}-P_{\mathrm{del}}$, which in the regime of overall network growth satisfies $0<\hat{I}\cdot \le 1$ and in the regime of overall network contraction $-1\le \hat{I}\cdot <0$. Using the master equation and computer simulations we show that for $-1<\hat{I}\cdot <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<\hat{I}\cdot \le 1$. Thus, the PARD model has a phase transition at $\hat{I}\cdot =0$, which separates between two structurally distinct phases. At the transition, for $\hat{I}\cdot =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