- What do slime mold, airline traffic, fungi, cancer tumors, and computer networks have in common? They all transport something -- nutrients, planes, or information -- from one place to another.
Although there are many examples of systems that solve the classic problem of getting from point A to point B, the extent to which decentralized, or perimeter routes, versus centralized, or hub-like routes benefit the complicated networks of the real world remains an open question.
Researchers from Oxford University in England have tackled the problem by examining the congestion costs within a network model that combines paths that go around the perimeter of the network and central hubs that provide shorter paths through the network. Real-world networks are too complicated to describe exactly mathematically. The researchers' model is simple enough to solve exactly, yet realistic enough to provide insights into real networks.
The research is aimed at finding ways to ease bottlenecks in networks involving manufacturing, the Internet and traffic, and ways to disrupt networks like tumor blood flow and terrorist supply chains. The findings could also help design better networks.
. . . .
In each case, the same interplay between centralized and decentralized pathways and control arises. "Going through the center has the advantage of shorter distance but has a higher risk of congestion and hence longer overall journey-time," said Johnson. "Going around the center has a lower risk of congestion but a larger geographical distance," he said.
. . . .
The model is a busy wheel-and-spoke road network that feeds cars into the center at a steady rate. The cars experience a bottleneck in the center which adds a delay or cost to the journey time, said Johnson. At the same time, cars that travel around the ring road typically have to travel further, but experience no cost.
"So the question is, for a given cost, what is the optimal number of roads carrying traffic into the center -- where optimal means that a driver going from A to B and free to use the ring road, the roads to the center, or some combination of the two -- will typically have the shortest journey time?" said Johnson.
The details of the roads in the city center will determine exactly what time delay drivers using the hub will experience, said Johnson. The number of roads feeding cars into the center, and hence how many cars are being fed into the center also affects the cost, he said.
In the simplest case no delay arises, the cost is zero, and it is always better to add more roads through the center. When the cost increases with the number of roads to the center, however, there is an optimal value for the number of roads, said Johnson. For a 1,000-node network with a cost-per-connection to the hub of 1, the optimal number of connections to the hub is 44.
The model showed that above a certain number of roads to the center, adding a new road always increases the bottleneck to such an extent that the added benefit of a new route is outweighed by the time delay due to increased congestion in the center. "The interesting and counter-intuitive result that we found is that in such situations we should actually reduce the number of roads connecting to the center," said Johnson.
The problem can also be turned on its head, said Johnson. "Given the number of roads which exists to the center and which we assume cannot easily be changed, what cost should be imposed for passing through the center [so] that drivers between A and B experience a minimum journey time," he said. "This charge could be an artificially induced time-delay -- lights or ramps with long waiting times -- or monetary."
The researchers' model showed that in London, where a flat fee of five pounds is charged for passing through the center, a usage-dependent cost would make the network more efficient. "These costs could be advertised on electronic boards around the ring road so that people decide ahead of time whether to use the center or not," said Johnson.
The model shows that the structure of a network is only part of the story of why systems work the way they do, said Johnson. In biological systems, and perhaps also in technological ones, it might be possible for a network to spontaneously rewire itself to respond to traffic. "Maybe this is what we are observing in nature when we see, for example, that different fungi have different types of network shapes," said Johnson.
"Taking it to a more speculative level, maybe... the network structures that we observe in nature have their structure emerging from their function rather than the other way round," said Johnson.
Emergent Order: Road Pricing and Urban Form
Hayek devotees and fans of books like Steven Johnson's Emergence -- which discusses the concept of emergent order in biological systems, computer science, and cities -- will certainly enjoy this article. Research on a new transportation network model offers some interesting findings regarding variable road pricing: