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

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 model, in which at each time step, with probability P_{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_{del}=1-P_{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}. For 0<η≤1 the overall process is of network growth, while for -1≤η<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 η_{c}(m)=-(m-2)/(m+2) such that for η_{c}(m)<η≤1 the degree distribution P_{t}(k) converges toward a stationary distribution P_{st}(k). In the special case of pure growth, where η=1, the model is reduced to a preferential attachment growth model and P_{st}(k) exhibits a power-law tail, which is a characteristic of scale-free networks. In contrast, for η_{c}(m)<η<1 the distribution P_{st}(k) exhibits an exponential tail, which has a well-defined scale. This implies a phase transition at η=1, in contrast with the preferential-attachment-random-deletion model [Budnick et al., J. Stat. Mech. (2025) 0134011742-546810.1088/1742-5468/ad99c7], in which the power-law tail remains intact as long as η>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} the stationary degree distribution P_{st}(k) lasts indefinitely, for η_{c}(m)<η<0 (and m>2) it persists for a finite lifetime, until the network vanishes. It is also found that in the regime of -1≤η≤η_{c}(m) the time-dependent degree distribution P_{t}(k) does not converge toward 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.