The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion

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_{add}$ and a random node deletion step takes place with probability $P_{del}=1-P_{add}$. The balance between the growth and contraction processes is captured by the parameter $\eta =P_{add}-P_{del}$. The case of pure network growth is described by $\eta =1$. In case that $0<\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 $-1<\eta <0$, the overall process is of network contraction, while in the special case of $\eta =0$ the expected size of the network remains fixed, apart from fluctuations. Using the master equation 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_{st}(k)$. In the case of pure network growth ($\eta =1$) the asymptotic distribution $P_{st}(k)$ follows an exponential distribution, while for $-1<\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<\eta <1$) the degree distribution $P_t(k)$ eventually converges to $P_{st}(k)$. In the case of overall network contraction ($-1<\eta <0$) we identify two different regimes. For $-1/3<\eta <0$ the degree distribution $P_t(k)$ quickly converges towards $P_{st}(k)$. In contrast, for $-1<\eta <-1/3$ the convergence of $P_t(k)$ is initially very slow and it gets closer to $P_{st}(k)$ only shortly before the network vanishes.

39 pages, 9 figures

References in corpus (6)

• Percolation of localized attack on complex networks
• Structural Transitions in Dense Networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• The distribution of shortest path lengths in a class of node duplication network models
• Cascading collapse of online social networks
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes

Cited by in corpus (2)

• Phase transition in evolving networks that combine preferential attachment and random node deletion
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment