The effect of preferential node deletion on the structure of networks that evolve via preferential attachment

Abstract

We present analytical results for the effect of preferential node deletion on the structure of networks that evolve via node addition and preferential attachment. To this end, we consider a preferential-attachment-preferential-deletion (PAPD) model, in which at each time step, with probability $P_{\mathrm{add}}$ there is a growth step where an isolated node is added to the network, followed by the addition of $m$ edges, where each edge connects a node selected uniformly at random to a node selected preferentially in proportion to its degree. Alternatively, with probability $P_{\mathrm{del}}=1-P_{\mathrm{add}}$ there is a contraction step, in which a preferentially selected node is deleted and its links are erased. The balance between the growth and contraction processes is captured by the growth/contraction rate $\eta =P_{\mathrm{add}}-P_{\mathrm{del}}$. For $0<\eta \le 1$ the overall process is of network growth, while for $-1\le \eta <0$ the overall process is of network contraction. Using the master equation and the generating function formalism, we study the time-dependent degree distribution $P_t(k)$. It is found that for each value of $m>0$ there is a critical value ${\eta }_c(m)=-(m-2)/(m+2)$ such that for ${\eta }_c(m)<\eta \le 1$ the degree distribution $P_t(k)$ converges towards a stationary distribution $P_{\mathrm{st}}(k)$. In the special case of pure growth, where $\eta =1$, the model is reduced to a preferential attachment growth model and $P_{\mathrm{st}}(k)$ exhibits a power-law tail, which is a characteristic of scale-free networks. In contrast, for ${\eta }_c(m)<\eta <1$ the distribution $P_{\mathrm{st}}(k)$ exhibits an exponential tail, which has a well-defined scale.This implies a phase transition at $\eta =1$, in contrast with the preferential-attachment-random-deletion (PARD) model [B. Budnick, O. Biham and E. Katzav, J. Stat. Mech. 013401 (2025)], in which the power-law tail remains intact as long as $\eta >0$.

arXiv comment38 pages, 10 figures

References in corpus (27)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Mixing patterns in networks
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Component sizes in networks with arbitrary degree distributions
• Structural Transitions in Dense Networks
• Metric structure of random networks
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Analytical results for the distribution of shortest path lengths in random networks
• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in a class of node duplication network models
• Cascading collapse of online social networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi 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
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion
• Analytical results for the in-degree and out-degree distributions of directed random networks that grow by node duplication
• Phase transition in evolving networks that combine preferential attachment and random node deletion