🌀 nonlinear sciences

The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion

This paper presents analytical results for the time-dependent and asymptotic degree distributions of networks evolving under a balance of random node addition and deletion, revealing that while growing networks converge to a steady-state distribution with a Poisson-like tail, contracting networks exhibit distinct convergence behaviors depending on the specific rate of contraction relative to the network's eventual disappearance.

Original authors: Barak Budnick, Ofer Biham, Eytan Katzav

Published 2026-08-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Barak Budnick, Ofer Biham, Eytan Katzav

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

For decades, scientists have been fascinated by how connections form and break in the complex webs that make up our world, from the neurons in a human brain to the friendships on a social media platform. These networks are not static; they are living systems that constantly change. In many cases, we understand how they grow: new members arrive and link up with existing ones, often creating a few highly connected hubs and many isolated individuals. This process of expansion is well documented. However, the opposite scenario—how a network shrinks when members leave randomly—has received far less attention, even though it is crucial for understanding everything from the collapse of power grids to the gradual loss of brain cells in aging and disease. While we know that removing too many parts can cause a system to shatter, the subtle changes that happen in the middle of that shrinking process, before the final collapse, have remained a mystery.

A team of researchers at the Hebrew University in Jerusalem has now filled in this gap by studying a mathematical model of a network that is simultaneously growing and shrinking. They imagined a system where, at every step, a new node is added and linked to random existing nodes, but at the same time, a random node is removed along with all its connections. The outcome of this tug-of-war depends entirely on the balance between the rate of addition and the rate of deletion. If new nodes arrive faster than they leave, the network grows. If they leave faster, the network shrinks. If the rates are perfectly matched, the size stays roughly the same. The researchers used advanced mathematical tools to track how the "degree" of the nodes—the number of connections each one has—evolves over time under these competing forces.

Their work reveals that the structure of these networks changes in surprising ways depending on the balance of growth and loss. When the network is purely growing, the distribution of connections settles into a predictable pattern that decays slowly. However, the moment even a tiny amount of random deletion is introduced, the nature of the network changes fundamentally. Instead of the slow decay seen in pure growth, the connections begin to follow a pattern that looks more like a random scatter, similar to the way connections are distributed in a completely random network. This shift happens immediately, no matter how small the rate of deletion is, marking a sharp transition in the network's architecture.

The study also uncovered a second, more subtle transition that occurs when the network is shrinking. The researchers found that the speed at which the network's structure adapts to this shrinking depends on how fast the deletion is happening. When the deletion rate is low, the network quickly settles into a stable, shrinking pattern that looks like a random web. But when the deletion rate is high, the network resists this change for a long time. It holds onto its original structure for most of its life, only snapping into the new, random-like pattern in the very final moments before it disappears completely. This creates a distinct divide between networks that adapt quickly to loss and those that hold on until the end.

These findings were not just theoretical guesses; the researchers built computer simulations to test their equations, and the results matched their predictions with high precision. They showed that the behavior of these networks is not a smooth, continuous slide from one state to another, but rather a series of distinct phases separated by critical tipping points. One transition marks the shift from pure growth to a mix of growth and loss. Another marks the shift from a growing network to a shrinking one. A third, more dynamic transition separates the fast-adapting shrinking networks from the slow-adapting ones.

The implications of this work extend beyond abstract mathematics. Because the model uses random deletion, it applies to scenarios where failures or departures are not targeted at specific, important nodes but happen by chance. This is relevant for understanding how social networks lose users due to general disinterest, how gene networks change as organisms lose genetic material, or how the brain loses neurons during normal aging and neurodegenerative diseases. The research suggests that the way a network collapses is not just a matter of losing pieces, but of how the remaining pieces reorganize themselves in the face of that loss. Depending on the speed of the loss, the network might reorganize quickly and efficiently, or it might cling to its old structure until the very last second. This distinction helps explain why some systems fail gradually while others seem to hold together until they suddenly fall apart.

By mapping out these different phases, the study provides a clearer picture of the life cycle of complex systems. It shows that the path a network takes as it grows or shrinks is determined by a few key parameters, and that small changes in the rate of addition or removal can lead to dramatically different outcomes. The researchers have provided a complete mathematical description of these processes, offering a new lens through which to view the stability and fragility of the interconnected systems that surround us. Their work confirms that even in a chaotic process of random addition and deletion, there is a hidden order and a predictable structure waiting to be discovered.

Technical Summary of "The structure of networks that evolve under a combination of growth, via node addition and random attachment, and contraction, via random node deletion"

Problem Statement
The paper addresses the structural evolution of complex networks subject to competing processes of growth and contraction. While extensive literature exists on pure network growth (e.g., preferential attachment leading to scale-free networks) and pure network contraction (e.g., random node deletion leading to Erdős-Rényi structures), the intermediate regime where both processes occur simultaneously has not been fully characterized, particularly regarding the transition between growth and contraction. The authors investigate a model where networks evolve via the addition of isolated nodes with random attachment and the random deletion of existing nodes. The primary objective is to derive the time-dependent degree distribution $P_t(k)$ and identify phase transitions in the network's structural and dynamical behavior based on the balance between these opposing rates.

Methodology
The authors employ a rigorous analytical approach combining the master equation formalism with generating functions:

Model Definition: The network evolves in discrete time steps. With probability $P_{add}$ , an isolated node is added, followed by the addition of $m$ edges connecting pairs of existing random nodes. With probability $P_{del} = 1 - P_{add}$ , a random node and its incident edges are deleted.
Control Parameter: The balance between growth and contraction is quantified by $\eta = P_{add} - P_{del}$ $η = P_{a dd} - P_{d e l}$ .
- $\eta = 1$ : Pure growth.
- $0 < \eta < 1$ : Net growth.
- $\eta = 0$ : Fixed average size.
- $-1 < \eta < 0$ : Net contraction.
- $\eta = -1$ : Pure contraction.
Master Equation: A master equation is derived for the time evolution of the number of nodes of degree $k$ , $N_t(k)$ . This accounts for node addition, edge attachment, node deletion, and the reduction of neighbor degrees upon deletion.
Generating Function: To solve the coupled differential equations, the authors introduce the generating function $G_t(u) = \sum u^k P_t(k)$ . This transforms the master equation into a first-order inhomogeneous linear partial differential equation.
Solution: Using the method of characteristics, the authors obtain a closed-form solution for $G_t(u)$ , from which the time-dependent degree distribution $P_t(k)$ is extracted. The solution is expressed as a sum of a term dependent on the initial condition (which decays over time) and an asymptotic term independent of initial conditions.

Key Results
The analytical derivation yields a closed-form expression for $P_t(k)$ that reveals three distinct phase transitions:

Structural Phase Transition at $\eta = 1$ :
- For pure growth ( $\eta = 1$ ), the asymptotic degree distribution $P_{st}(k)$ follows an exponential (geometric) distribution.
- For any rate of deletion ( $\eta < 1$ ), the asymptotic distribution changes qualitatively. It consists of a sum of Poisson-like terms and exhibits a Poisson-like tail. The authors note that even an infinitesimal rate of node deletion ( $\eta \to 1^-$ ) induces a structural change from an exponential to a Poisson-like distribution. This transition corresponds to a singularity in the differential equation for the generating function.
Growth-Contraction Transition at $\eta = 0$ :
- This transition separates the regime of overall network growth ( $\eta > 0$ ) from overall contraction ( $\eta < 0$ ).
- While the analytical expression for $P_t(k)$ remains formally identical across this boundary, the behavior of the decay coefficient $\alpha_t$ differs fundamentally. For $\eta > 0$ , the network grows indefinitely, and the memory of the initial condition decays asymptotically. For $\eta < 0$ , the network vanishes at a finite time $t_{vanish}$ , and the decay of the initial condition memory is bounded by this finite lifetime.
Dynamical Transition at $\eta = -1/3$ :
- Within the contraction regime ( $-1 < \eta < 0$ ), a transition occurs at $\eta = -1/3$ regarding the convergence speed to the asymptotic distribution $P_{st}(k)$ .
- Slow Contraction ( $-1/3 < \eta < 0$ ): The degree distribution $P_t(k)$ converges relatively quickly to $P_{st}(k)$ and remains in its vicinity for a significant portion of the network's remaining lifetime.
- Fast Contraction ( $-1 < \eta < -1/3$ ): The convergence is initially very slow. The distribution $P_t(k)$ only approaches $P_{st}(k)$ shortly before the network vanishes. This is characterized by a discontinuity in the time derivative of the weight coefficient $w_t$ at $t_{vanish}$ .

Validation
The analytical results are validated against computer simulations. The simulations show very good agreement with the analytical predictions for both the steady-state distributions and the time-dependent evolution across various values of $\eta$ . Specifically, the simulations confirm the slow convergence near $\eta = 1$ and the distinct dynamical behaviors on either side of $\eta = -1/3$ .

Significance and Claims
The paper claims to provide the first comprehensive analytical description of networks evolving under simultaneous growth and random contraction. Its significance lies in:

Unified Framework: Providing a single closed-form expression for the degree distribution that applies to both growing and contracting regimes.
Identification of Phase Transitions: Explicitly identifying three phase transitions (structural at $\eta=1$ , growth/contraction at $\eta=0$ , and dynamical at $\eta=-1/3$ ) that define the network's structural and temporal behavior.
Insight into Intermediate States: The work elucidates the concept of "intermediate asymptotic states" in contracting networks. It demonstrates that for certain deletion rates, the network exhibits a stable structural form ( $P_{st}(k)$ ) for a finite duration before disintegration, whereas for higher deletion rates, the network collapses before this structure can emerge.
Sensitivity to Deletion: The results highlight that the introduction of even a minimal rate of random node deletion fundamentally alters the nature of the steady-state degree distribution from exponential to Poisson-like, a finding that challenges the robustness of purely growth-based models.

The authors conclude that their analytical results are in very good agreement with simulations, offering a precise mathematical understanding of how the interplay between node addition and deletion shapes network topology.

More like this