The New Laws of Explosive Networks
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.”
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.)
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 Wired.com.
