Phase transition in evolving networks that combine preferential attachment and random node deletion

Barak Budnick, Ofer Biham, Eytan Katzav · 2024

Read Phase transition in evolving networks that combine preferential attachment and random node deletion by Barak Budnick, Ofer Biham, Eytan Katzav (2024) 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-2412-14549.txt.

Introduction

Barak Budnick, Ofer Biham, and Eytan Katzav analyze networks that grow by attachment yet also lose nodes at random. Their 2024 paper defines the PARD model: at each step a new node links preferentially to well connected nodes, or a random node is deleted. A single parameter captures whether growth or shrinkage wins overall.

Using a master equation and computer simulations, the authors map the steady distribution of node degrees on both sides. When the network shrinks overall, the degree distribution settles with an exponential tail. When it grows, the tail follows a power law instead. The switch between them is a phase transition at the balance point. Such models fit real networks whose members also leave, from online platforms to citation graphs.

Catalog record

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

Source: https://arxiv.org/abs/2412-14549

Browse the full library · About the Tower of Babel

Full text

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

Phase transition in evolving networks that combine preferential attachment and random node deletion Barak Budnick, Ofer Biham, Eytan Katzav Abstract Analytical results are presented for the structure of networks that evolve via a preferential-attachment-random-deletion (PARD) model in the regime of overall network growth and in the regime of overall contraction. The phase transition between the two regimes is studied. At each time step a node addition and preferential attachment step takes place with probability P add P_{\rm add} , and a random node deletion step takes place with probability P del = 1 − P add P_{\rm del}=1-P_{\rm add} . The balance between growth and contraction is captured by the parameter η = P add − P del \eta=P_{\rm add}-P_{\rm del} , which in the regime of overall network growth satisfies 0 < η ≤ 1 0<\eta\leq 1 and in the regime of overall network contraction − 1 ≤ η < 0 -1\leq\eta<0 . Using the master equation and computer simulations we show that for − 1 < η < 0 -1<\eta<0 the time-dependent degree distribution P t ​ ( k ) P_{t}(k) converges towards a stationary form P st ​ ( k ) P_{\rm st}(k) which exhibits an exponential tail. This is in contrast with the power-law tail of the stationary degree distribution obtained for 0 < η ≤ 1 0<\eta\leq 1 . Thus, the PARD model has a phase transition at η = 0 \eta=0 , which separates between two structurally distinct phases. At the transition, for η = 0 \eta=0 , the degree distribution exhibits a stretched exponential tail. While the stationary degree distribution in the phase of overall growth represents an asymptotic state, in the phase of overall contraction P st ​ ( k ) P_{\rm st}(k) represents an intermediate asymptotic state of a finite life span, which disappears when the network vanishes. , , Keywords : Network growth models, preferential attachment, node deletion, degree distribution, scale-free networks. 1 Introduction Network theory provides a conceptual and mathematical framework for the analysis of structure and dynamics in biological, social and technological networks [ 1 , 3 , 4 , 5 , 2 , 6 ] . It was found that empirical networks are typically small-world networks whose diameters scale logarithmically with the network size. Many of these networks exhibit fat-tailed degree distributions with scale free structures [ 7 , 8 , 9 ] . The growth processes that yield these structures were studied extensively. It was found that the added nodes tend to connect preferentially to nodes of high degree, which are more visible or prominent in the network. As a result, nodes of high degree tend to attract new connections at a higher rate. Highly connected nodes (or hubs) often provide better access to information, resources or opportunities within the network. New nodes tend to benefit from these advantages by connecting to high degree nodes, further reinforcing their centrality. The preferential attachment mechanism gives rise to scale-free networks with power-law degree distributions of the form P(k)\sim k^{-\gamma} [ 8 , 9 , 10 , 11 ] . These properties are captured by the Barabási-Albert (BA) model [ 8 ] . In this model, at each time step a new node is added to the network and connects to m of the existing nodes. The probability of an existing node of degree k to gain a link to the new node is proportional to k . The degree distribution of the BA network exhibits a power-law tail with \gamma=3 . Variants of the BA model were shown to yield power-law distributions with exponents in the range 2<\gamma\leq 3 [ 10 , 11 , 12 ] . In scale-free networks of a finite size, there is always a maximum degree k_{\rm max} , which is constrained by the network size N . For \gamma\leq 2 the mean degree \langle K\rangle diverges in the limit of k_{\rm max}\rightarrow\infty . For 2<\gamma<3 the mean degree is bounded while the second moment \langle K^{2}\rangle diverges algebraically. In the marginal case of \gamma=3 the second moment diverges logarithmically, while in the regime of \gamma>3 it is bounded. The robustness of complex networks is crucial for ensuring functionality, security and stability of these networks. The mathematical framework of percolation theory provides useful tools for the analysis of network robustness against the deletion of nodes due to failures and attacks [ 15 , 13 , 14 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 ] . When the number of deleted nodes exceeds some threshold, the network disintegrates, resulting in a large number of disconnected components [ 27 , 28 , 15 , 13 , 14 , 25 , 26 ] . In this context, it was shown that scale-free networks are resilient to random failures and attacks targeting random nodes [ 13 ] , but are vulnerable to targeted attacks aimed at high degree nodes or hubs [ 14 ] . The evolution of the structure of networks that undergo contraction due to node deletion processes was recently studied [ 29 , 30 ] . These processes include random, preferential and propagating node deletion. The process of random node deletion describes random failures or random attacks that do not target any specific type of nodes. The process of preferential node deletion describes attacks that target high degree nodes, where the probability of a node to be selected for deletion is proportional to its degree. Propagating node deletion describes processes that propagate in the network from an infected node to its neighbors. Using the master equation for the degree distribution P_{t}(k) , it was shown that for a broad class of network structures, when the network contracts, its degree distribution evolves towards a Poisson distribution, namely it becomes an Erdős-Rényi (ER) network [ 31 , 32 , 33 ] . ER networks belong to an ensemble of maximum entropy random graphs [ 34 ] . The structure of networks that evolve under a combination of growth and contraction processes was studied in Refs. [ 35 , 37 , 36 ] , which focus on the regime of overall network growth. More specifically, in the model studied by Moore et al. [ 35 ] the growth mechanism is based on the BA model [ 8 ] , where each new node is connected to m existing nodes, which are selected preferentially, while the contraction process takes place via random node deletion. We thus refer to the model studied by Moore et al. [ 35 ] as the Barabási-Albert with random deletion (BARD) model. It was found that in the regime of overall network growth the asymptotic degree distribution of the BARD model exhibits a power-law tail. However, the complementary regime, in which the overall process is of network contraction has not been studied. The case of overall network contraction occurs when the rate of node deletion exceeds the rate of node addition. For example, social networks contract when the number of users that leave the network is larger than the number of users that join [ 38 , 39 ] . A similar situation may occur in networks of business firms in which the nodes

Read the complete text