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

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 add , and a random node deletion step takes place with probability P del = 1 − P add . The balance between growth and contraction is captured by the parameter η = P add − P del , which in the regime of overall network growth satisfies 0 < η ⩽ 1 and in the regime of overall network contraction − 1 ⩽ η < 0 . Using the master equation and computer simulations we show that for − 1 < η < 0 the time-dependent degree distribution P t ( k ) converges towards a stationary form P st ( k ) which exhibits an exponential tail. This is in contrast with the power-law tail of the stationary degree distribution obtained for 0 < η ⩽ 1 . Thus, the PARD model has a phase transition at η = 0, which separates between two structurally distinct phases. At the transition, for η = 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 st ( k ) represents an intermediate asymptotic state of a finite life span, which disappears when the network vanishes.