Complex Systems

The New Laws of Explosive Networks

Researchers are uncovering the hidden laws that reveal how the Internet grows, how viruses spread, and how financial bubbles burst.

Paolo Čerić/PATAKK

Networks grow as individual nodes connect to one another. By tweaking the rules that govern when nodes connect, researchers can shape the network’s properties.

Last week, United Airlines grounded nearly 5,000 flights when its computer system crashed. The culprit: a faulty network router. Later on the same morning, another computer glitch halted trading on the New York Stock Exchange for over three hours.

Some saw the sinister hand of a hacker in these outages, but they are far more likely to be a coincidence, an intrinsic feature of the system rather than a bug. Networks go down all the time, a consequence of unprecedented levels of interconnection. Disruptions can occur even in the most robust networks, whether these are power grids, global financial markets, or your favorite social network. As the former Atlantic reporter Alexis Madrigal observed when a computer error shut down the Nasdaq stock exchange in 2013, “When things work in new ways, they break in new ways.”

A fresh new understanding of such systems — the way they grow, and how they break — has arisen from the physics of coffee.

Researchers usually think of network connectivity as happening in a slow, continuous manner, similar to the way water moves through freshly ground coffee beans, slowly saturating all the granules to become coffee in the container below. However, over the past few years, researchers have discovered that in special cases, connectivity might emerge with a bang, not a whimper, via a phenomenon they have dubbed “explosive percolation.”

Courtesy of Raissa D'Souza

Clusters grown via explosive percolation.

This new understanding of how über-connectivity emerges, which was described earlier this month in the journal Nature Physics, is the first step toward identifying warning signs that may occur when such systems go awry — for example, when power grids begin to fail, or when an infectious disease starts to mushroom into a global pandemic. Explosive percolation may help create effective intervention strategies to control that behavior and, perhaps, avoid catastrophic consequences.

An Explosive Twist

Traditional mathematical models of percolation, which date back to the 1940s, view the process as a smooth, continuous transition. “We think of percolation as water flowing through the ground,” said Robert Ziff, a physicist at the University of Michigan who has been studying phase transitions for the past 30 years. “It’s a formation of long-range connectivity in the system.”

The formation of connectivity can be understood as a phase transition, the process whereby water freezes into ice or boils away into vapor.

Phase transitions are ubiquitous in nature, and they also provide a handy model for how individual nodes in a random network gradually link together, one by one, via short-range connections over time. When the number of connections reaches a critical threshold, a phase shift causes the largest cluster of nodes to grow rapidly, and über-connectivity results. (Seen this way, the percolation process that gives rise to your morning cup of joe is an example of a phase transition. Hot water passes through roasted beans and shifts into a new state — coffee.)

Kevin Tong, UC Davis

Raissa D’Souza, a physicist at the University of California, Davis, is exploring how small-scale interventions can alter a large, complex network.

Explosive percolation works a bit differently. The notion arose during a workshop in 2000 at the Fields Institute for Research in Mathematical Sciences in Toronto. Dimitris Achlioptas, a computer scientist at the University of California, Santa Cruz, proposed a possible means for delaying a phase transition into a densely connected network, by merging the traditional notion of percolation with an optimization strategy known as the power of two choices. Instead of just letting two random nodes connect (or not), you consider two pairs of random nodes, and decide which pair you prefer to connect. Your choice is based on predetermined criteria — for instance, you might select whichever pair has the fewest pre-existing connections to other nodes.

Because a random system would normally favor those nodes with the most pre-existing connections, this forced choice introduces a bias into the network — an intervention that alters its typical behavior. In 2009, Achlioptas, Raissa D’Souza, a physicist at the University of California, Davis, and Joel Spencer, a mathematician at New York University’s Courant Institute of Mathematical Sciences, found that tweaking the traditional percolation model in this way dramatically changes the nature of the resulting phase transition. Instead of arising from a slow, steady continuous march toward greater and greater connectivity, connections emerge globally all at once throughout the system in a kind of explosion — hence the moniker “explosive percolation.”

The concept has exploded in its own right, spawning countless papers over the past six years. Many of the papers debate whether this new model constitutes a truly discontinuous phase transition. Indeed, in 2011 researchers showed that for the particular model analyzed in the original 2009 study, explosive transitions only happen if the network is finite. While networks such as the Internet have at most about a billion nodes, phase transitions are most commonly associated with materials, which are intricate lattices of so many molecules (approximately 1023 or more) that the systems are effectively infinite. Once extended to a truly infinite system, explosive percolations appear to lose some of their boom.

Yet D’Souza and her cohorts have not been idle either. They have uncovered many other percolation models that do yield truly abrupt transitions. These new models share a key feature, according to D’Souza. In traditional percolation, nodes and pairs of nodes are chosen at random to form connections, but the likelihood of two clusters merging is proportional to their size. Once a large cluster has formed, it dominates the system, absorbing any smaller clusters that might otherwise merge and grow.

However, in the explosive models, the network grows, but the growth of the large cluster is suppressed. This allows many large but disconnected clusters to grow, until the system hits the critical threshold where adding just one or two extra links triggers an instantaneous switch to über-connectivity. All the large clusters combine at once in a single violent merger.

A New Paradigm for Control

D’Souza wants to learn how to better control complex networks. Connectivity is a double-edged sword, according to her. “For normal operating systems [like the Internet, airline networks or the stock exchange], we want them to be heavily connected,” she said. “But when we think about epidemics spreading, we want to curtail the extent of the connectivity.” Even when high connectivity is desirable, it can sometimes backfire, causing a potentially catastrophic collapse of the system. “We’d like to be able to intervene in the system easily to enhance or delay its connectivity,” depending on the situation, she said.

Explosive percolation is a first step in thinking about control, according to D’Souza, because it provides a means of manipulating the onset of long-range connectivity via small-scale interactions. A series of small-scale interventions can have dramatic consequences — for good or ill.

Public relations professionals often ask how D’Souza’s work might help their products go viral. She typically responds by pointing out that her models actually suppress viral behavior, at least in the short term. “Do you want to eke out all the gains as quickly as you can, or do you want to suppress [growth] so when it does happen, more people learn about it right away?” she said. The same holds true for political campaigns, according to Ziff. Following this model, they would spend much of their time early in the campaign on grassroots local efforts, building up localized clusters of connections and suppressing the emergence of long-range connections until the campaign was ready to go national with a big media splash.

In other systems, such as financial markets or electrical power grids, when a collapse occurs, it is likely to be catastrophic, and this patchwork approach could be used to reverse the process, breaking up the über-connected system into a collection of disjointed clusters, or “islands,” to avoid catastrophic cascading failures. Ideally, one would hope to find a “sweet spot” for the optimal level of intervention.

In power grids, utility companies lose money every time a line goes down, so ideally one should try to prevent any downtime. Yet acting to avoid any outage whatsoever can inadvertently lead to very large outages that are far more costly. Thus, encouraging small cascading “failures” can dissipate energy imbalances that would otherwise have caused massive failures later on, a potentially smart strategy even though it eats into profit margins. “If you frequently trigger small cascades, you never get really massive events, but you [sacrifice] all that short-term profit,” D’Souza explained. “If you prevent cascades at all costs, you might make a lot of profit, but eventually a cascade is going to happen, and it will be so massive it [could] wipe out your entire profit.”

The next step is to identify signs that may indicate when a system is about to go critical. Researchers understand phase transitions like the ones that happen when water turns to ice, and can identify signs of an impending change. The same cannot be said for explosive percolation. “Once we have a better understanding, we’ll be able to see how our control interventions are impacting the system,” D’Souza said. “We will have this data we can analyze in real time to see if we are seeing the signature of the early warning signals from many different classes of transitions.”

Phase transitions have fascinated physicists and mathematicians alike for decades, so why has this explosive behavior been found only now? D’Souza thinks it’s because the breakthrough required the merging of ideas from several fields, most notably Achlioptas’ idea to blend algorithms and statistical physics, thereby creating an exciting new modeling phenomenon. “It really is a new paradigm of percolation,” Ziff said.

This article was reprinted on

View Reader Comments (18)

Leave a Comment

Reader CommentsLeave a Comment

  • The key feature for network resiliency is plasticity. In metallurgical terms; ‘ductility’ and ‘malleability’. When systems become too stiff, they become brittle – and break. This is how diamonds are cleaved, which are >10x harder than #2 in hardness.

    A 40hr workweek is less than 25% of the 168 hours in a week. Two shifts are <50%. JIT mfg is highly efficient, but too brittle, with no room for hiccups. There is an optimal, which is not 100%.

    Optimal system plasticity would be an insightful read.

  • Such a fabulous article. My congratulations to Achlioptas and D’Souza; explosive percolation in systems has great import. Consider corporate multi-national takeovers, “Once a large cluster has formed, it dominates the system, absorbing any smaller clusters that might otherwise merge and grow.” And the EU and issues with Greece, “If you prevent cascades at all costs, you might make a lot of profit, but eventually a cascade is going to happen, and it will be so massive it [could] wipe out your entire profit.” These new discoveries apply to all systems, across all disciplines, and especially when making coffee.

  • The article reminded me of slime mold time lapse videos. Some of the punctuated growth spurts might be examples of different percolation model settings. Here are a couple videos:

  • Maybe it’s just my coming from an EE background, but I’m missing something from the discussion about systems:
    1) Feedback loops
    2) Damping
    3) Perturbation
    4) Control theory
    5) State Table analysis
    6) Constraint or limit theory
    7) Chaos theory

    It is my understanding that these would have an influence over behavior of any system. Then again, I did graduate many years ago.

  • Continuing Shelley Hartman’s comment re: stock mergers (and agglomeration of capital). Gov’t regulation may correspond to a modified percolation step.

  • Fascinating article, I wonder what insights it might give into the way political networks grow and cohere and (apparently) suddenly become the norm – is there a point of transition which marks the phases of lots of small networks and the rapid emergence of a coherent majority? What role does social media play in creating the critical size of network? Does this theory have implications for the understanding of the phenomenon of terrorism and how to counter it effectively?

  • Might this relate to, or the same underlying “rule” be at play with, “punctuated equilibrium” in evolutionary theory?

  • I don’t like math and physics but this article kept me interested throughout. Here is an article from MIT that seems to show the flipside of explosive growth in social networks.

  • Fantastic article, thank you. This connection between graphs and phase transitions is fascinating, and I really wonder what the limits are. I wonder if, for example, phase transitions can be a bridge to using quantum field theory correlation functions to make predictions about real-world networks.

  • Very interesting article. I wonder if Tracy Widom distributions can be used to predict. See

  • The reasonably well-known states of matter include solid, liquid, gas and plasma (and some quantum states). I cannot imagine that ‘coffee’ – even if percolated – could be described as a new “state” of water, as it is in this article. On that basis: beer, whisky and wine would qualify as new states of water.

  • as a retired lab worker cum social scientist I always get mentally frustrated when in the end- the whole reason of the article drifts off and -as a next step-in this article without qualification or talk of a new paradigm without any results or speculations thereof making the whole article somewhat more vacuous than its authors and contributors intended

  • Fascinating. I had a hunch that I was in fact reading an account relating the big bang, inflation, the universe cooling and expanding, symmetry breaking and phase transitions with the emergence of spacetime which itself feels like a giant complex network with the rules for light cones, affective pasts etc. This work looks like it is really onto something big.

  • Interesting stuff. The crashes at United Airlines and NYSE were due to an external trigger or internal? Or is it that any system that outgrows itself suffers a sudden transition? I would like to recommend an excellent book titled "Critical Mass" by Philip Ball that provides a great insight into some of these ideas.

  • Very nice article. And very nice work on explosive networks by the related authors. I wonder if the explosiveness and the phase transition arises when the scale-free modular architecture is lost due to a couple of links that tend to couple otherwise non-heavily interconnected modules. As this coupling could destroy modularity at some point, its main benefits are lost as well, mainly resilience and the compartment-type structure that avoids easy global contagion. Put another way, is this explosiveness somehow related to what happens when the network goes from a scale-free modular network to a pure scale-free network?

  • There is a fundamental dilemma for physics, that nature displays innumerable clearly "constructive" developmental processes, that physics finds inexplicable… for two reasons. One is that physics only studies numerical processes. It's partly a "chicken and egg" problem of having given so little attention to patterns of natural design to be unaware of how curious they are. It's also that the mathematical tools physics relies on have no way to describe normal observable constructive processes like biological or economic growth, etc. Once you look at them as a natural phenomenon, of developing organization, 'growth' emerges as a stunningly complex yet smoothly progressive **chain reaction emergent design**, producing new forms of natural organization spontaneously. You need to study such such autonomous complex processes to have meaningful questions about them.

    Unless a new generation with interest in the constructive patterns of naturally occurring design comes along, a science like physics with curiosity only for computational theories, seems at a dead end. That states a big problem, but in a solvable way. Physics needs to accumulate the baseline observations needed to develop theories of natural design, but has not shown any interest in that at all. I've tried and tried for decades. There IS as way, though, following the enormous economic success of "object oriented" software, that developed unexpectedly using strategies from Christopher Alexander's method for describing holistic architectural designs. Physics COULD learn from its own most successful computational spin-offs, that demonstrate to build like and link with natural designs.

Comments are closed.