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

Barak Budnick, Ofer Biham and Eytan Katzav · 2025

Read The effect of preferential node deletion on the structure of networks that evolve via preferential attachment by Barak Budnick, Ofer Biham and Eytan Katzav (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-16574.txt.

Introduction

Barak Budnick, Ofer Biham, and Eytan Katzav study in 2025 what happens when busy nodes are also the ones most often deleted from a growing network. In their model, new nodes join and link to busy nodes, while other steps remove busy nodes and all their links.

A single rate sums up the balance between growth and shrinkage. The authors use a master equation and generating functions to track how the share of nodes with each link count changes over time. Above a key threshold rate, that share settles to a fixed shape. In pure growth the shape has a heavy power law tail, while with some deletion the tail turns exponential.

Catalog record

CREATORBarak Budnick, Ofer Biham and Eytan Katzav
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-16574

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The effect of preferential node deletion on the structure of networks that evolve via preferential attachment Barak Budnick, Ofer Biham and Eytan Katzav 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 add P_{\rm add} there is a growth step where an isolated node is added to the network, followed by the addition of m 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 del = 1 − P add P_{\rm del}=1-P_{\rm 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 η = P add − P del \eta=P_{\rm add}-P_{\rm del} . For 0 < η ≤ 1 0<\eta\leq 1 the overall process is of network growth, while for − 1 ≤ η < 0 -1\leq\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 ) P_{t}(k) . It is found that for each value of m > 0 m>0 there is a critical value η c ( m ) = − ( m − 2 ) / ( m + 2 ) \eta_{c}(m)=-(m-2)/(m+2) such that for η c ​ ( m ) < η ≤ 1 \eta_{c}(m)<\eta\leq 1 the degree distribution P t ​ ( k ) P_{t}(k) converges towards a stationary distribution P st ​ ( k ) P_{\rm st}(k) . In the special case of pure growth, where η = 1 \eta=1 , the model is reduced to a preferential attachment growth model and P st ​ ( k ) P_{\rm st}(k) exhibits a power-law tail, which is a characteristic of scale-free networks. In contrast, for η c ​ ( m ) < η < 1 \eta_{c}(m)<\eta<1 the distribution P st ​ ( k ) P_{\rm st}(k) exhibits an exponential tail, which has a well-defined scale. This implies a phase transition at η = 1 \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 η > 0 \eta>0 . These results illustrate the sensitivity of evolving networks to preferential node deletion, in contrast with their robustness to random node deletion. While for η ≥ max ⁡ { η c ​ ( m ) , 0 } \eta\geq\max\left\{\eta_{c}(m),0\right\} the stationary degree distribution P st ​ ( k ) P_{\rm st}(k) lasts indefinitely, for η c ​ ( m ) < η < 0 \eta_{c}(m)<\eta<0 (and m > 2 m>2 ) it persists for a finite lifetime, until the network vanishes. It is also found that in the regime of − 1 ≤ η ≤ η c ​ ( m ) -1\leq\eta\leq\eta_{c}(m) the time-dependent degree distribution P t ​ ( k ) P_{t}(k) does not converge towards a stationary form, but continues to evolve until the network is reduced to a set of isolated nodes. These results provide insight on the structure of transient social networks, such as dating networks and job-seeking platforms, in which user turnover is intrinsically high. pacs 64.60.aq,89.75.Da I Introduction It is well established that the preferential attachment mechanism plays a prominent role in the growth process of complex networks found in natural, social and technological systems [ 1 , 2 , 3 ] . Previous studies have shown that the preferential attachment process gives rise to networks that exhibit scale-free structures with power-law degree distributions. The preferential attachment process is captured by the Barabási-Albert (BA) model [ 4 , 5 ] . In this model, at each time step a new node is added to the network and forms links to m existing nodes, which are selected preferentially, namely with probabilities that are proportional to their degrees [ 4 , 5 ] . The degree distribution of the BA network exhibits a power-law tail of the form P(k)\propto k^{-\gamma} , where \gamma=3 [ 4 , 5 , 6 , 7 ] . In the case of \gamma=3 the mean degree \langle K\rangle is finite while the second moment \langle K^{2}\rangle diverges logarithmically. This is a hallmark of scale-free networks, where a small number of hubs exhibit disproportionately high degrees compared to other nodes. A side effect of this property is a great vulnerability to attacks that target the hubs [ 8 , 9 ] , in contrast to its resilience to random node failures [ 8 , 10 ] . In practice, network growth is often accompanied by the loss of nodes, which may be due to inadvertent failures, deliberate attacks or propagating infections. Social network contract when the number of users that leave the network is larger than the number of users that join [ 11 , 12 ] . The reasons for leaving the network may be loss of interest, concerns about privacy or migration to other social networks. It is thus important to examine the effect of node deletion on the emerging structure of a growing network. In this context, several studies have focused on the effect of random node deletion on the structure of networks that grow via preferential attachment [ 13 , 15 , 14 ] . It was found that as long as the evolution of the network is dominated by the growth process (namely, the node addition rate exceeds the deletion rate) the power-law tail of the degree distribution is maintained. However, it was recently found that in the opposite regime, in which the rate of node deletion exceeds the rate of node addition, the degree distribution converges towards a stationary form which exhibits an exponential tail [ 16 ] . This stationary degree distribution persists for a finite period of time, until the network vanishes. The emergence of such intermediate asymptotic state was observed in an empirical study by Saavedra et al. [ 17 ] , who examined the business network of New York City’s garment industry. In this network nodes represent designers and contractors and links denote collaborative productions. Over a period of 19 years (1985–2003), the network experienced a reduction in size by more than an order of magnitude. Despite this decline, the network maintained its structural integrity and resisted rapid fragmentation. Its degree distribution remained stationary, displaying a truncated power-law behavior. The study revealed that the deletion process acted in an anti-preferential manner, rendering low-degree nodes more vulnerable to removal. Concurrently, a partial recovery via preferential attachment was observed. Such resilience is indicative of the ability of complex networks to preserve functionality amid significant contraction. The case of preferential node deletion provides a useful framework for the analysis of targeted attacks [ 9 ] . In this process, one selects a random edge and deletes one of its end-nodes together with its links. This is equivalent to selecting the nodes for deletion in proportion to their degree, such

Read the complete text