Connections Get You Everywhere, but Slowly
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.