Focus

Connections Get You Everywhere, but Slowly

Phys. Rev. Focus 20, 15
Large networks like the Internet may remain connected after many broken links, but they may not be very effective.
Well connected. A map of a portion of MBone, an internet overlay network for video and other high-bandwidth uses (height of arcs represents distance). Networks like this can remain connected even after many broken links, but they may no longer be effective.

The Internet and other large networks can hang together as connected wholes even when 10% or more of their communication links are knocked out, according to some mathematical studies. But in the 2 November Physical Review Letters, researchers suggest that some networks may not be so resilient. Networks must provide more than mere connection; they have to let information or other resources move from point to point quickly and effectively. The researchers argue that after a few links fail, the routes between some points can become so long as to be unusable. The effect could make networks fail even when simpler analyses would suggest they’d still be working.

A network is any collection of things linked together by connections of some sort. The Internet is a collection of computers linked by communication lines, while an ecosystem consists of species linked by relationships of predator and prey. In mathematical terms, researchers have known that it takes surprisingly few links to integrate isolated islands into one connected whole. Imagine 1000 cities that need to be connected by roads. Although the number of possible roads between pairs of cities is nearly 500,000, calculations show that it takes just over 500 roads, built between cities at random, to connect most of them. With, say, 1000 roads, a driver could go almost anywhere quite easily, taking only a handful of roads. And the transportation system would be fairly resilient because it could lose almost half of its links before many cities would be cut off.

But this system is not as robust as it might seem, say Eduardo López of the Los Alamos National Laboratory and his colleagues. Remove some of those 1000 roads, and travel gets harder, especially if the number dwindles toward that crucial 500, which mathematicians call the percolation threshold. Near that point, the road network, while still technically covering most cities, may nevertheless fail as a transportation system, as drivers spend days traveling many roads just to get between two cities.

To explore this effect in detail, the physicists monitored how the distance between elements in simulated networks increased as they destroyed network links at random. They supposed that if the distance, measured as the shortest path between two points, became too large–say, more than one and a half times its original value–the path between would become effectively useless. They found that a network can become disconnected, in practical terms, long before it becomes physically disconnected. For example, in a typical simulation, a network that mostly hung together as a connected whole even after 60% of its links were removed, fell apart in practical terms after only 30% were removed.

But this effect can be positive as well as negative, says López. Viruses and other infectious diseases travel through social networks, along human-to-human contacts. “Public health officials estimate the level of vaccination or other intervention using the conventional percolation threshold,” aiming to break an epidemic’s connectivity, he says. But in conditions where a virus can only travel through a limited number of carriers–such as the summertime for the flu–vaccination could make the virus’s travel paths so long that an epidemic fades away before spreading widely. Knowing this could allow authorities to use scarce vaccine supplies more wisely.

The new theory gives more realistic estimates of network stability, says Santo Fortunato of the Institute for Scientific Interchange in Torino, Italy. “This work goes beyond the simple idea of ‘Is the network connected or not?’”

–Mark Buchanan

Mark Buchanan is a freelance science writer who splits his time between Abergavenny, UK, and Notre Dame de Courson, France.

More Information


Subject Areas

Nonlinear Dynamics

Related Articles

Time Delays Improve Performance of Certain Neural Networks
Computational Physics

Time Delays Improve Performance of Certain Neural Networks

Both the predictive power and the memory storage capability of an artificial neural network called a reservoir computer increase when time delays are added into how the network processes signals, according to a new model. Read More »

The Neuron vs the Synapse: Which One Is in the Driving Seat?
Complex Systems

The Neuron vs the Synapse: Which One Is in the Driving Seat?

A new theoretical framework for plastic neural networks predicts dynamical regimes where synapses rather than neurons primarily drive the network’s behavior, leading to an alternative candidate mechanism for working memory in the brain. Read More »

Nonreciprocal Frustration Meets Geometrical Frustration
Nonlinear Dynamics

Nonreciprocal Frustration Meets Geometrical Frustration

New theoretical work establishes an analogy between systems that are dynamically frustrated, such as glasses, and thermodynamic systems whose members have conflicting goals, such as predator–prey ecosystems. Read More »

More Articles