Structure of networks that evolve under a combination of growth and contraction

Abstract

We present analytical results for the emerging structure of networks that evolve via a combination of growth (by node addition and random attachment) and contraction (by random node deletion). To this end we consider a network model in which at each time step a node addition and random attachment step takes place with probability ${P}_{\mathrm{add}}$ and a random node deletion step takes place with probability ${P}_{\mathrm{del}}=1\ensuremath{-}{P}_{\mathrm{add}}$. The balance between the growth and contraction processes is captured by the parameter $\ensuremath{\eta}={P}_{\mathrm{add}}\ensuremath{-}{P}_{\mathrm{del}}$. The case of pure network growth is described by $\ensuremath{\eta}=1$. In the case that $0<\ensuremath{\eta}<1$, the rate of node addition exceeds the rate of node deletion and the overall process is of network growth. In the opposite case, where $\ensuremath{-}1<\ensuremath{\eta}<0$, the overall process is of network contraction, while in the special case of $\ensuremath{\eta}=0$ the expected size of the network remains fixed, apart from fluctuations. Using the master equation and the generating function formalism, we obtain a closed-form expression for the time-dependent degree distribution ${P}_{t}(k)$. The degree distribution ${P}_{t}(k)$ includes a term that depends on the initial degree distribution ${P}_{0}(k)$, which decays as time evolves, and an asymptotic distribution ${P}_{\mathrm{st}}(k)$ which is independent of the initial condition. In the case of pure network growth ($\ensuremath{\eta}=1$), the asymptotic distribution ${P}_{\mathrm{st}}(k)$ follows an exponential distribution, while for $\ensuremath{-}1<\ensuremath{\eta}<1$ it consists of a sum of Poisson-like terms and exhibits a Poisson-like tail. In the case of overall network growth ($0<\ensuremath{\eta}<1$) the degree distribution ${P}_{t}(k)$ eventually converges to ${P}_{\mathrm{st}}(k)$. In the case of overall network contraction ($\ensuremath{-}1<\ensuremath{\eta}<0$) we identify two different regimes. For $\ensuremath{-}1/3<\ensuremath{\eta}<0$ the degree distribution ${P}_{t}(k)$ quickly converges towards ${P}_{\mathrm{st}}(k)$. In contrast, for $\ensuremath{-}1<\ensuremath{\eta}<\ensuremath{-}1/3$ the convergence of ${P}_{t}(k)$ is initially very slow and it gets closer to ${P}_{\mathrm{st}}(k)$ only shortly before the network vanishes. Thus, the model exhibits three phase transitions: a structural transition between two functional forms of ${P}_{\mathrm{st}}(k)$ at $\ensuremath{\eta}=1$, a transition between an overall growth and overall contraction at $\ensuremath{\eta}=0$, and a dynamical transition between fast and slow convergence towards ${P}_{\mathrm{st}}(k)$ at $\ensuremath{\eta}=\ensuremath{-}1/3$. The analytical results are found to be in very good agreement with the results obtained from computer simulations.

Topics & Concepts