🔬 physics

Evolving Networks Created by Preferential Attachment and Decay

This paper proposes a method to extend preferential attachment growth models to allow for the continuous addition and removal of edges in evolving networks while preserving their power-law degree distribution.

Original authors: Justin Downes

Published 2026-01-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Justin Downes

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

Imagine a bustling city where people (nodes) are constantly arriving, leaving, and changing who they know (edges). In the real world, friendships and connections aren't static; they grow, fade, and shift every day. However, for a long time, computer scientists trying to simulate these networks used a very rigid method: they would add a new person, give them a few friends, and then freeze those friendships forever.

This paper by Justin Downes tackles a problem: What happens if we let the network breathe? What if, while new people arrive, existing people also make new friends and lose old ones?

Here is the breakdown of the paper's journey, using simple analogies:

1. The Problem: The "Frozen" City

Most existing models for growing networks work like a one-way street. You add a new person, and they connect to popular people (a concept called Preferential Attachment—the "rich get richer"). Once that connection is made, it never changes.

But real life isn't like that. In a real social network, you might meet a new friend today, but you might also drift apart from an old one tomorrow. The author found that if you try to simply add and remove connections randomly in these models, the network breaks. It stops looking like a real social network (which has a few super-popular hubs and many average people) and starts looking like a boring, average bell curve where everyone has roughly the same number of friends.

2. The Solution: The "Inverted" Dance

The author wanted to build a model where the network could evolve (add and remove edges) but still keep that special "Power Law" shape (the few hubs, many small nodes).

To do this, they tried a clever trick. They realized that if you just let people randomly pick new friends, the popular people will keep getting more popular, and the less popular people will get stuck. To fix this, the author introduced a "Reverse Preference" rule for removing connections.

The Analogy: Imagine a dance floor.
- Adding a partner: When a new dancer joins, they naturally gravitate toward the most popular people already dancing (Preferential Attachment).
- Breaking up: The author realized that to keep the dance floor balanced, you can't just break up random couples. You have to specifically target the less popular dancers to break up their connections.
- Why? Because the popular dancers are constantly getting new partners. If you don't occasionally "cut the ties" of the less popular dancers, the whole system gets skewed. By intentionally removing edges from the "underdogs," the model prevents the popular nodes from hoarding all the connections, keeping the distribution healthy.

3. The Three Models Tested

The author tested this "Add and Subtract" method on three different types of network growth rules:

Barabási-Albert: The basic "rich get richer" model.
Bianconi-Barabási: A version where some nodes are just "more attractive" (like having a great personality) regardless of how many friends they already have.
Relevance Model: A version where older nodes slowly lose their "relevance" or attractiveness over time, like a celebrity fading from the spotlight.

4. The Results

The experiment was a success, but with a twist:

The Basic Model: When the author applied the "reverse" rule to the basic model, it struggled a bit and started to look more like a normal, average distribution (everyone having similar numbers of friends).
The Complex Models: The more complex models (the ones with "attractiveness" scores and "decay" functions) did a much better job. They managed to keep their "Power Law" shape even while edges were constantly being added and removed.

The author notes that the Relevance Model was the most successful at maintaining the power law structure, almost becoming more power-law-like as it evolved. However, there is a catch: if you run this model for too long, the "decay" function eventually wears everyone out, and the system stops working.

5. What Didn't Work

The author also tried a different approach: instead of changing which edges get removed, they tried to change the "attractiveness" (fitness) of the nodes over time, hoping the nodes would naturally adjust to keep the balance. This failed. The network just collapsed into a boring, average distribution. It turns out, you can't just tweak the "personality" of the nodes; you have to actively manage the connections themselves.

The Bottom Line

This paper demonstrates that you can simulate a living, breathing network where connections are constantly made and broken, without losing the unique "scale-free" structure that real-world networks have. The secret sauce? When adding connections, follow the crowd (preferential attachment), but when removing connections, target the less popular ones (inverse preference).

This allows scientists to create better simulations of social networks without needing to wait for perfect real-world data, helping them understand how these complex systems evolve over time.

Technical Summary: Evolving Networks Created by Preferential Attachment and Decay

Problem Statement
Existing growth models for synthetic networks, particularly those based on preferential attachment (e.g., Barabási-Albert), typically generate scale-free structures by adding nodes and edges sequentially, where new edges are "frozen" and never removed. While this accurately models static structures like citation networks, it fails to capture the dynamics of real-world social networks, where edges are continuously created and removed even as new nodes join. When standard preferential attachment models are naively extended to allow for edge removal, the resulting node degree distribution rapidly loses its scale-free (power-law) structure, often devolving into a normal distribution. This paper addresses the challenge of evolving a network—adding and removing edges between existing nodes—while preserving the power-law degree distribution characteristic of the original growth model.

Methodology
The study implements three foundational growth models using Python and the NetworkX package:

Barabási-Albert (BA): Standard preferential attachment where new edges connect to existing nodes with probability proportional to their degree ( $k_i$ ).
Bianconi-Barabási (BB): Extends BA by introducing a fitness value ( $\eta_i$ ) for each node, allowing nodes to attract edges based on intrinsic fitness in addition to degree.
Relevance Model: Extends BB by adding a time-decay function ( $f_R(\tau)$ ) that penalizes older nodes, simulating the decay of interest over time.

All base models were grown to a size of 10,000 nodes with 3 edges per new node. Following the growth phase, an Evolution Model was applied for 300 time steps. In each step, approximately 1,000 edges were added and 1,000 edges were deleted to maintain a constant edge count.

Edge Addition: Followed the specific growth rules of the underlying base model (BA, BB, or Relevance).
Edge Deletion (The Core Innovation): To prevent the network from collapsing into a normal distribution, the authors developed an "inverted" selection mechanism for edge removal. Instead of deleting edges randomly or based on the same preferential attachment logic used for growth, the probability of deleting an edge connected to a node is inversely proportional to that node's degree (and fitness/decay parameters).
- The deletion probability $\Pi^d_i$ is calculated by subtracting the node's weighted degree from the maximum degree in the network (plus a small constant $\beta$ to ensure non-zero probability for high-degree nodes).
- This mechanism biases the removal of edges from lower-degree nodes, counteracting the natural tendency of preferential attachment to concentrate edges on high-degree nodes.

Key Results
The study evaluated the degree distributions of the networks before and after the 300-step evolution phase:

Barabási-Albert Model: The evolved network showed a transition away from a power-law distribution toward a more normal distribution, though the shift was gradual.
Bianconi-Barabási Model: This model maintained a power-law distribution better than the BA model but still showed signs of transitioning toward a normal distribution (reduction in both very high and very low degree nodes).
Relevance Model: Surprisingly, this model appeared to achieve a distribution even more power-law-like after evolution than it had at the start. The authors attribute this to the interaction between the decay function and the inverted deletion mechanism.

The results suggest that the more parameters a model possesses (BA has none, BB has fitness, Relevance has fitness and decay), the better it preserves the desired distribution during evolution.

Significance and Claims
The paper claims to demonstrate a two-stage approach where networks can be evolved (edges added and removed) while adhering to preferential attachment principles and maintaining a scale-free structure.

Simulation Utility: The primary significance is the ability to generate synthetic data that mimics the dynamic nature of real social networks (edge churn) without losing the scale-free property. This allows researchers to develop and refine computational social science models using simulated data before accessing real-world datasets, which are often restricted by privacy and granularity issues.
Methodological Contribution: The paper provides a specific mechanism (inverted deletion probability) that allows for edge evolution without destroying the power-law distribution, a capability lacking in standard extensions of preferential attachment models.
Limitations: The authors acknowledge that the model is an approximation and that the specific decay function used in the Relevance model has practical limits (eventually all nodes reach a floor value). The paper does not provide an analytic solution to these methods, noting that deriving one is a potential future endeavor.

Negative Findings
The paper explicitly notes that attempts to evolve the fitness values themselves (treating them as dynamic biological traits) failed to maintain a power-law distribution, resulting instead in normal distributions. This reinforces the necessity of the specific edge-deletion mechanism proposed rather than dynamic parameter adjustment.