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.

arXiv comment39 pages, 9 figures

References in corpus (34)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• Resilience of the Internet to random breakdowns
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Immunization of complex networks
• Connectivity of Growing Random Networks
• Generation of uncorrelated random scale-free networks
• Network dismantling
• Dynamically induced cascading failures in power grids
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Percolation of localized attack on complex networks
• Duplication-divergence model of protein interaction network
• Log-Networks
• Fast and simple decycling and dismantling of networks
• Structural Transitions in Dense 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
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Spreading of localized attacks in spatial multiplex networks
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Cliques and duplication-divergence network growth
• The distribution of shortest path lengths in a class of node duplication network models
• 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
• Tailored graph ensembles as proxies or null models for real networks II: results on directed graphs
• 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