🌀 nonlinear sciences

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

本文提出了对偏好附着-偏好删除（PAPD）网络模型的解析结果，证明了演化网络的结构稳定性与度分布关键取决于增长率与收缩率之间的平衡，并存在一个特定的临界阈值，决定了网络是保持有限规模还是无限增长。

原作者： Barak Budnick, Ofer Biham, Eytan Katzav

发布于 2026-08-21

📖 1 分钟阅读☕ 轻松阅读

原作者： Barak Budnick, Ofer Biham, Eytan Katzav

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在人们连接、分享和寻求机会的广阔数字景观中，网络并非静态的地图，而是不断增长与萎缩的、有生命力的实体。研究这些复杂系统的科学家早已知晓，新的连接往往基于受欢迎程度而形成：一个人的朋友越多，他们建立新联系的可能性就越大。这种被称为“优先连接”（preferential attachment）的倾向，解释了为什么一些在线平台会发展出少数超连接的枢纽（hubs），而大多数用户却只有寥寥数个链接。然而，现实世界的网络很少仅仅是在增长；它们也会失去成员。人们在找到伴侣后会离开交友软件，或是在找到工作后退出招聘平台。虽然研究人员已经理解了随机离开如何影响这些系统，但一个关键问题仍悬而未决：如果离开的人不是随机的，而是特别受欢迎且连接最紧密的成员，情况会发生什么？

耶路撒冷希伯来大学的一个物理学家团队致力于通过构建一个数学模型来回答这个问题，该模型模拟了一个既有新成员加入、又有旧成员离开且遵循特定规则的网络。在他们的模拟中，新用户到达并连接到现有成员，但他们更有可能链接到那些已经拥有许多连接的人。相反，当网络萎缩时，它并非随机失去成员；相反，它优先移除那些连接最紧密的个体，从而有效地针对那些维系结构的枢ло（hubs）。研究人员通过调整这两个力量之间的平衡——即网络的增长率与收缩率——来追踪网络形态的变化。

研究揭示了这些网络行为中存在着一个尖锐且令人惊讶的分水岭。当网络处于纯粹增长状态，或者增长速度快于萎缩速度时，其结构会稳定在一个模式中，即少数高度连接的枢纽占据主导地位，形成许多著名社交网络所特有的“无标度”（scale-free）形态。然而，一旦研究人员引入哪怕极微小的“优先删除”——即移除最受欢迎的节点——整个结构就会发生改变。网络不仅仅是失去了它的枢纽；它发生了根本性的转变。网络不再是由少数超连接节点和许多孤立节点组成，而是连接变得分布得更加均匀，极端的枢纽也消失了。网络对任何单一用户的连接数产生了一个自然限制，从而形成了一种更加均匀、且不像纯粹增长系统中那样容易出现极端不平等现象的结构。

这种转变并非渐进的，它代表了一种明显的相变（phase transition）。研究人员发现，只要网络在增长，它就能保持其无标度特性。但一旦过程转向包含对受欢迎节点的优先移除，网络就会失去其无标度特征，并采用一种新的、具有明确连接规模限制的稳定形式。这凸显了这些系统演化过程中极其敏锐的敏感性。虽然众所周知，网络对于随机故障具有鲁棒性（即它们可以经受住许多普通用户的随机离开），但当离开的过程针对那些连接最紧密的成员时，它们却显得异常脆弱。即使是向移除受欢迎节点倾斜的一丁点偏差，也足以彻底拆解无标度架构，将幂律尾部（power-law tail）替换为伽马分布（Gamma distribution），后者虽然仍有尾部，但是有界的而非无界的。

这项工作的意义延伸到了对瞬时社交网络（如用于约会或求职的网络）生命周期的理解。在这些环境中，用户通常带着特定的目标加入。一旦实现目标，他们就会离开。由于最成功的用户通常也是最活跃和连接最紧密的，他们往往是目标达成后最可能离开平台的群体。该模型表明，这种自然的成功与离开的循环，使得这些网络永远无法发展出像永久性社交平台那样由枢纽主导的极端结构。相反，它们会稳定在一个更平衡的状态，其中连接分布得更加均匀，没有任何一个用户能够变得压倒性的强大。

研究人员还探索了当网络整体在萎缩时会发生什么。他们发现，如果优先删除的速率足够高，网络最终会完全崩溃，消解为一群没有任何连接的孤立个体。存在一个临界阈值，在此之下，网络无法维持自身；低于此点，结构会随时间推移而瓦解，直至一无所有。然而，高于此阈值时，网络可以长期维持一个虽不同但稳定的结构，即便它正在缓慢萎缩。这种稳定性仅在网络拥有足够成员来维持进程时存在，但它最终会达到一个点，即剩余用户太少以至于无法形成新的链接，从而走向一个最终的、寂静的终结。

通过数学分析和计算机模拟的结合，这项研究为定向移除如何重塑数字世界提供了一个清晰的图景。它表明，管理谁离开网络的规则与管理谁加入网络的规则同样重要。研究结果挑战了“网络天然对所有形式的扰动都具有韧性”的假设，揭示了它们在面对针对其最成功成员的特定类型扰动时，其实是非常脆弱的。对于在线平台的开发者而言，这提供了一个看待用户留存的新视角：平台将人们连接到其目标的成功本身，可能会在无意中加速其自身的结构变化，将其从枢纽主导的模型推向一个更平衡、但也可能更脆弱的状态。

技术摘要：演化网络中的优先节点删除

问题陈述
虽然优先连接机制已被公认为驱动无标度网络结构（如 Barabási-Albert 模型）的核心机制，但演化网络中“优先节点删除”（preferential node deletion）对结构的后果仍不为人所熟知。以往的研究探讨了随机节点删除，发现只要增长过程占据主导地位，无标度特性就会持续存在。然而，许多现实世界的系统（例如社交平台、求职网站等瞬态社交网络）涉及高用户流失率，其中高连接度的节点在达成目标后更有可能离开。本文研究了优先节点删除（即以与度数成正比的概率移除节点）对通过节点添加和优先连接进行演化的网络度分布的影响。

方法论
作者引入了优先连接-优先删除（PAPD）模型。网络在离散时间步内演化，包含两种可能的事件：

增长步骤（概率为 $P_{add}$ ）： 添加一个孤立节点，随后添加 $m$ 条边。每条边将一个均匀随机选择的节点与一个优先选择（与其度数成正比）的节点相连。
收缩步骤（概率为 $P_{del} = 1 - P_{add}$ ）： 优先选择一个节点（与其度数成正比）并将其及其关联边一并删除。

这两类过程之间的平衡由增长/收缩率 $\eta = P_{add} - P_{del}$ 控制。作者允许 $m$ 为非整数，以确保连续的相图。

为了分析该系统，作者推导了关于时间相关度分布 $P_t(k)$ 的主方程。该推导采用了忽略相邻节点间度-度相关性的平均场近似。分析利用生成函数形式（ $G(u)$ ）来求解大规模网络极限下的平稳度分布 $P_{st}(k)$ 。通过以 Erdős-Rényi 网络初始化的计算机模拟，对解析结果的有效性进行了交叉验证。

核心贡献与结果

平稳相的存在性：
研究确定了一个临界阈值 $\eta_c(m) = -(m-2)/(m+2)$ 。

对于 $\eta_c(m) < \eta \leq 1$ ，时间相关度分布 $P_t(k)$ 收敛于平稳分布 $P_{st}(k)$ 。
对于 $\eta < \eta_c(m)$ ，不存在平稳解；网络持续演化直至瓦解为一组孤立节点（吸收态）。

在 $\eta = 1$ 处的结构相变：
一个主要发现是在纯增长极限（ $\eta = 1$ ）处存在结构相变：

纯增长（ $\eta = 1$ ）： 平稳分布恢复了标准的无标度行为，具有特征性的幂律尾部 $P_{st}(k) \sim k^{-3}$ ，这与 Barabási-Albert 模型一致。
混合增长/收缩（ $\eta_c(m) < \eta < 1$ ）： 即便是极微小的优先删除率也会破坏幂律尾部。平稳分布呈现出指数尾部（具体为 Gamma 分布形式 $P_{st}(k) \sim k^{-\gamma} e^{-k/k_{cut}}$ ），并具有明确的尺度。这与涉及随机删除的模型形成了鲜明对比，在随机删除模型中，对于任何 $\eta > 0$ ，幂律尾部都会持续存在。

收缩机制下的有限寿命：
在 $\eta_c(m) < \eta < 0$ 的机制下（即收缩占主导但并非完全收缩），平稳分布 $P_{st}(k)$ 仅在有限寿命内存在，直到网络消失。这被描述为一种“中间渐近态”。对于 $\eta < \eta_c(m)$ ，网络在达到平稳形式之前就会瓦解。
网络属性：

异质性（Disassortativity）： 模拟显示 PAPD 网络是异质的（负的度-度相关性），即高出度节点倾向于连接低出度节点。这归因于非对称的加边机制（均匀到优先）。
渗透（Percolation）： 平稳相对应于包含巨分量的超临界网络。平稳相与瓦解相之间的边界与 Molloy-Reed 判据预测的渗透转变相一致，尽管度相关性使精确位置变得复杂。

解析表达式：
论文提供了关于平均度 $\langle K \rangle$ 的平稳度分布 $P_{st}(k)$ 的闭合形式表达式，其中使用了超几何函数。同时，作者还推导了在 $\eta \to \eta_c(m)$ 和 $\eta \to 1$ 附近平均度的近似值。

意义与主张
作者声称，这些结果说明了演化网络对优先节点删除的敏感性，这与它们对随机节点删除的已知鲁棒性形成对比。从无标度结构向有尺度结构（指数分布）的转变，在引入优先删除后立即发生，前提是增长率并非纯粹的最大值（ $\eta < 1$ ）。

本文的研究结果为瞬态社交网络（如交友和求职平台）的结构提供了见解，这类网络具有高用户流失率（“流失/Churn”）。在这些系统中，由于成功的用户（高连接度节点）更有可能离开，网络结构预计将遵循具有指数尾部的 Gamma 分布，而非无标度的幂律分布。这挑战了“优先连接机制总能产生无标度网络”的假设，强调了节点移除的具体性质（优先 vs 随机）会从根本上改变网络的渐近拓扑结构。

类似论文