Budnick Barak, Biham Ofer, Katzav Eytan
The Hebrew University, Racah Institute of Physics, Jerusalem 9190401, Israel.
Phys Rev E. 2025 Jun;111(6-1):064312. doi: 10.1103/mch5-63j9.
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.
我们给出了关于优先节点删除对通过节点添加和优先连接而演化的网络结构影响的分析结果。为此，我们考虑一个优先连接 - 优先删除模型，其中在每个时间步，以概率(P_{add})存在一个增长步骤，即一个孤立节点被添加到网络中，随后添加(m)条边，其中每条边将一个随机均匀选择的节点连接到一个根据其度优先选择的节点。或者，以概率(P_{del}=1 - P_{add})存在一个收缩步骤，其中一个优先选择的节点被删除并且其链接被擦除。增长和收缩过程之间的平衡由增长/收缩率(\eta = P_{add} - P_{del})来体现。对于(0 < \eta \leq 1)，整体过程是网络增长，而对于(-1 \leq \eta < 0)，整体过程是网络收缩。使用主方程和生成函数形式，我们研究随时间变化的度分布(P_{t}(k))。发现对于每个(m > 0)的值，存在一个临界值(\eta_{c}(m)=-(m - 2)/(m + 2))，使得对于(\eta_{c}(m) < \eta \leq 1)，度分布(P_{t}(k))趋向于一个平稳分布(P_{st}(k))。在纯增长的特殊情况下，即(\eta = 1)，该模型简化为一个优先连接增长模型，并且(P_{st}(k))呈现幂律尾部，这是无标度网络的一个特征。相反，对于(\eta_{c}(m) < \eta < 1)，分布(P_{st}(k))呈现指数尾部，其具有明确的尺度。这意味着在(\eta = 1)处存在一个相变，这与优先连接 - 随机删除模型[Budnick等人，《统计力学杂志》(2025) 0134011742 - 546810.1088/1742 - 5468/ad99c7]不同，在该模型中，只要(\eta > 0)，幂律尾部就保持不变。这些结果说明了演化网络对优先节点删除的敏感性，与其对随机节点删除的鲁棒性形成对比。虽然对于(\eta \geq \max{\eta_{c}(m),0})，平稳度分布(P_{st}(k))会无限期持续，但对于(\eta_{c}(m) < \eta < 0)（且(m > 2)），它会持续有限的寿命，直到网络消失。还发现，在(-1 \leq \eta \leq \eta_{c}(m))范围内，随时间变化的度分布(P_{t}(k))不会趋向于一个平稳形式，而是会持续演化，直到网络缩减为一组孤立节点。这些结果为诸如约会网络和求职平台等瞬态社交网络的结构提供了见解，在这些网络中用户更替本质上很高。
