In all networks, like road or airline traffic networks, the Internet, cancer tumors or industry supply chains, you need to pass packets from node to node, such as cars, information or data. But which are the most efficient, decentralized networks or hub-like centralized ones? According to Technology Research News (TRN), researchers from Oxford University, U. K., have designed a model which maps traffic congestion. This model combines roads going through the center of a city and other ones avoiding it. And they found that, from a cost point of view, it would be sometimes better to close roads going through cities than adding more. They also think that these conclusions can be applied to almost all kinds of networks, biological ones or created by humans. Read more.
Here are two of the opening paragraphs of the TRN article.
Researchers from Oxford University in England have tackled the problem [of network optimization] 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.
Below are two examples of networks, the first one being a model of traffic analysis, while the second one is a real natural network (Credit: Oxford University).
On the figure above, the model network shows transport pathways through the central hub (thick lines) and around the ring (thin lines). The graph itself shows there is an optimal value for the number of connections, in this case 44 connections for 1,000 nodes.
And this photon scintillation image shows the nutrient distribution within a laboratory-grown fungus Phanerochaete velutina. Nutrient density increases going from blue to green to red.
As you can see from the network model above, traffic congestion in a city would increase if the number of roads to the center also increases after a certain point.
Information networks straddle the world. Nothing remains concealed. But the sheer volume of information dissolves the information. We are unable to take it all in.
—Günther Grass (b. 1927)
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 Neil Johnson, Professor of Physics at Oxford University.
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 have applied their model to London, where you have to pay £ 5 to cross the center with your car, and concluded that such a flat fee leads to some inefficiencies.
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.
If you want to learn more about this research, the latest work has been published by Physical Review Letters in February 2005 under the title "Effect of Congestion Costs on Shortest Paths Through Complex Networks" (Volume 94, Number 5, Article 058701, February 11, 2005). Here are two links to the abstract and to the full paper -- thanks to arXiv.org (PDF format, 4 pages, 242 KB). The above illustrations come from this paper.
Finally, here is a link to an article from New Scientist about the same subject, "New roads can cause congestion," published on February 1, 2005
Sources: Kimberly Patch, Technology Research News, July 27/August 3, 2005; and various web sites
Related stories can be found in the following categories.
Nature
Networking
Physics
Social Networks
Transportation
And remember that comments are no longer accepted here because of a vandal. If you want to tell me something about this post, please go to the bottom right of this page and send me an e-mail.