Discontinuous transition in explosive percolation via local suppression

This paper demonstrates that a discontinuous transition in explosive percolation can emerge through local link suppression and finite-node rewiring, thereby extending the conditions for such transitions beyond the previously known requirement of global information and no rewiring.

The Gist

Imagine a giant party where people are standing in a room, and they are slowly forming groups by shaking hands with their neighbors.

In a normal party, as more people shake hands, these groups grow slowly and smoothly. Eventually, one massive group forms that includes almost everyone. This is a smooth transition.

But scientists have been studying a weird type of party called "Explosive Percolation." In this version, the guests try to be clever. Every time a new handshake is suggested, the guests look at the options and choose the one that prevents any single group from getting too big too fast. They are essentially playing a game of "don't let the giant group win."

For a long time, scientists thought that to stop the giant group from forming until the very last second (creating a sudden, explosive jump where everyone suddenly joins one giant group), the guests needed superpowers. They thought the guests needed to see every single possible handshake in the entire room (global information) to make the right choice. If they could only see their immediate neighbors (local information), the giant group would just form slowly, like a normal party.

This paper changes the rules of the game.

The author, Young Sul Cho, introduces a new rule: Link Rewiring.

The New Rule: "The Hot Potato"

Imagine you are at this party. A new handshake is added between two people. Suddenly, you (and your neighbors) realize this handshake might make your group too big.

In the old models, you were stuck with that handshake. But in this new model, you are allowed to drop your current handshakes and grab new ones with different people nearby to break up the big group.

Here is the magic trick:

1. The Spark: A new handshake happens.
2. The Ripple: The person closest to that new handshake feels the pressure. They drop their old handshakes and grab new ones to smaller groups.
3. The Wave: This causes their neighbors to feel the pressure too. They drop their handshakes and grab new ones. This wave of "dropping and grabbing" spreads outward like a ripple in a pond.
4. The Stop: The wave stops once the groups are balanced again.

The Big Discovery

The author tested this on two different types of party layouts:

1. The Tree Layout (The Bethe Lattice)
Imagine a family tree where everyone only has a few branches going down.

• The Result: Even though the "ripple" of people changing handshakes is limited to a small, finite number of people, the party still ends in a sudden explosion.
• The Analogy: It's like a line of dominoes. You only need to push a few dominoes to make the whole line fall, but in this case, the "falling" happens all at once at the very end. The author proved that you don't need to see the whole room to cause an explosion; you just need to be able to rearrange your immediate neighborhood.

2. The Two-Group Layout (The Bipartite Network)
Imagine a dance floor with two teams (Team A and Team B). People can only hold hands with someone from the opposite team.

• The Result: Here, the "ripple" of people changing handshakes gets bigger and bigger as you get closer to the explosion point. Near the end, almost everyone has to rearrange their handshakes to keep the groups small.
• The Analogy: It's like a game of musical chairs where the music stops. As the game gets closer to the end, the number of people scrambling for a seat becomes huge. But even though the "chaos" involves more people, the result is still the same: a sudden, discontinuous jump to one giant group.

Why This Matters

Before this paper, the scientific consensus was:

• No Rewiring + Local Info = Smooth transition (Boring).
• No Rewiring + Global Info = Explosive transition (Cool, but requires superpowers).
• Rewiring + Global Info = Explosive transition.

This paper proves:

• Rewiring + Local Info = Explosive transition!

The Takeaway

The paper shows that flexibility is more important than vision.

You don't need to be a genius who can see every possible connection in the world to create a sudden, dramatic change. You just need the ability to adapt locally. If people are allowed to quickly rearrange their connections to avoid big crowds, the system naturally builds up tension until it snaps, causing a sudden, explosive formation of a giant group.

It's like a traffic jam: If drivers can't change lanes (no rewiring), traffic flows smoothly until it stops. But if drivers are constantly weaving and changing lanes to avoid a big backup (local suppression), the traffic might flow fine for a long time, but then suddenly, everything gridlocks at once.

In short: By allowing nodes (people) to "rewire" their connections locally, we can trigger a sudden, explosive change without needing to know the whole picture. It turns a slow, boring process into a dramatic, sudden event.

Technical Summary

1. Problem Statement

The paper addresses a fundamental question in network science regarding Explosive Percolation (EP) and the nature of the Discontinuous Percolation Transition (DPT).

• Background: In standard EP models, links are added sequentially based on specific rules to suppress the growth of large clusters. Historically, it was established that a DPT (where the giant component jumps abruptly) only occurs if the model utilizes global information (an infinite number of link candidates) to select the optimal link. If only local information (a finite set of candidates) is used, the transition remains continuous, despite appearing abrupt.
• The Gap: Previous models did not allow nodes to rewire existing links once occupied. However, in real-world systems (e.g., quarantine protocols), nodes often rewire connections to avoid large clusters. While recent studies showed that allowing nodes to continuously rewire to a steady state could induce a DPT using local information, it remained unclear if a dynamical process—where links are added one by one and a finite number of nodes rewire immediately after each addition—could achieve a DPT.

2. Methodology

The author introduces a new dynamical EP model where link addition is followed by a sequential, localized rewiring process to suppress cluster growth. The study is conducted on two distinct network topologies:

A. The Model Rules

1. Link Addition: At each time step, one unoccupied link is randomly selected and occupied.
2. Local Suppression (Rewiring):
   • The node closest to the newly added link (the "initial rewiring node") initiates a rewiring process.
   • The node disconnects all its occupied links and reconnects them to neighbors in the lower layer (or outward direction) in ascending order of their cluster sizes.
   • Propagation: If a rewiring node's cluster size increases due to this change, its parent (neighbor in the upper layer) may need to rewire to maintain the ascending order. This process propagates outward/upward until a node is disconnected from its parent, at which point the process terminates.
3. Goal: The system attempts to reach a "steady state" (where nodes connect to smaller clusters first) after every single link addition, rather than waiting for a global equilibrium.

B. Network Topologies

1. Bethe Lattice Branch: A tree structure with constant degree $z=4$. Trees are acyclic, ensuring a unique path between nodes.
2. Bipartite Network: A network with two partitions where nodes in the first partition connect to random neighbors in the second. This structure contains loops (cycles), making it non-tree-like.

3. Key Contributions

• First Demonstration of DPT with Finite Local Information + Rewiring: The paper proves that a DPT can emerge in an EP model using only local information (finite link candidates) provided that link rewiring is permitted. This overturns the previous paradigm that global information was strictly necessary for a DPT in EP.
• Dynamical vs. Steady-State Equivalence: The study demonstrates that the order parameter (fraction of nodes in the giant component) in this dynamical, step-by-step rewiring model coincides with the theoretical steady-state solution, even though the number of rewiring nodes is finite at each step.
• Topology-Dependent Rewiring Behavior: The paper distinguishes how the number of rewiring nodes ($m$) behaves near the critical threshold ($p_c$) depending on the network structure:
  • Tree (Bethe Branch): $m$ remains finite even at $p_c$.
  • Non-Tree (Bipartite): $m$ is finite below $p_c$ but diverges as $p \to p_c$.

4. Key Results

On the Bethe Lattice Branch

• Transition: The order parameter $P_\infty(p)$ (probability the root belongs to the spanning cluster) exhibits a sharp, discontinuous jump at $p_c \approx 0.6528$.
• Rewiring Count: The number of nodes that rewire ($m$) after a single link addition increases monotonically but remains finite at the critical point $p_c$.
• Mechanism: Because the network is a tree, the propagation of rewiring is strictly linear. The system maintains a perfect "ordered state" (nodes connected to smallest clusters) throughout the process.

On the Bipartite Network

• Transition: The order parameter $G(p)$ (fraction of nodes in the largest cluster) also exhibits a DPT at $p_c \approx 0.6233$, matching the analytical steady-state prediction.
• Rewiring Count: The number of rewiring nodes $m$ diverges as $(p_c - p)^{-8/5}$ as the threshold is approached from below.
• Ordered State: Unlike the tree, the bipartite network contains loops. Consequently, a small fraction of nodes ($f$) fail to maintain the strict ascending order of cluster sizes due to conflicting connections. However, $f$ remains very small and vanishes in the thermodynamic limit ($N \to \infty$), allowing the DPT to persist.
• Physical Interpretation: The divergence of $m$ in the bipartite network is linked to the finite fraction of nodes in the macroscopic cluster at $p_c$, requiring an infinite number of local adjustments to suppress the giant component formation right at the threshold.

5. Significance and Implications

• Redefining Information Requirements: The study fundamentally changes the understanding of what is required for a discontinuous transition. It shows that local information is sufficient for a DPT if the system allows for dynamic link rewiring. This bridges the gap between theoretical models and real-world systems where nodes actively reconfigure connections (e.g., social networks, epidemic control).
• Mechanism of Suppression: The paper clarifies that the "explosive" nature arises not from the global selection of the best link, but from the local suppression of cluster growth via sequential rewiring.
• Universality of Rewiring: The results suggest that the ability of a network to undergo a DPT via local rules is robust across different topologies (trees and networks with loops), provided the rewiring mechanism is active.
• Theoretical Extension: This work extends previous findings (which required infinite candidates for DPT) by showing that the combination of local information and link rewiring creates a new universality class for explosive percolation.

In conclusion, Young Sul Cho demonstrates that link rewiring acts as a powerful mechanism to induce discontinuous percolation transitions using only local information, resolving a long-standing limitation in explosive percolation theory and offering new insights into the control of network connectivity.