Many man-made and natural networks have same underlying architecture

November 3, 2011

By Denise Brehm
Civil & Environmental Engineering

Complex networks as dissimilar in size, age and character as the metabolic processes of a yeast cell, the World Wide Web, and the airline system of the United States all share a similar underlying structure, said Professor Albert-László Barabási of Northeastern University in an Oct. 26 talk, the first in the Distinguished Engineering and Science Speaker Seminar Series (DES4) sponsored by the Department of Civil and Environmental Engineering (CEE).

“What is really amazing about this is that these networks — that differ both in nature and in age — have over time and through many different processes converged to a somewhat similar architecture as if the same designer tried to build them,” said Barabási, who is known for introducing the concept of scale-free networks in 1999 using the World Wide Web as an example.

A scale-free network is one in which the distribution of connections to nodes follows a power law, like the 80/20 rule often used to describe distribution of wealth among a population: 20 percent of the people own 80 percent of the wealth. In a scale-free network, there are a very few nodes that have many, many connections, and many, many nodes with only a few connections. A smattering of nodes have connections that fall somewhere between, but the distribution is largely polarized with the vast majority belonging to a few nodes.

In the U.S. airline system, for instance, airports serve as nodes and direct flights between them serve as connecting links. Airline hubs have many links, while smaller airports have very few.

As a scale-free network grows, the nodes with the most connections will continue to get a larger share of new connections than will less-popular nodes. Facebook is a good example of this “preferential attachment.” The website has exponentially more links than do most of the other trillion pages on the WWW. Barabási has also modeled the mechanism describing how one enormous hub can overcome another, in this case Facebook overtaking Google as the largest hub on the Web.

But the large hubs that characterize a scale-free network also form its Achille’s heel, Barabási said. The random destruction of small hubs has little effect, but a network can be destroyed by an attack on a hub. “Scale-free networks are very robust to random failures, but very fragile to attacks,” he said.

Barabási, in work done with CEE Professor Marta González, also demonstrated that human mobility forms a scale-free network. Using information provided by cellphone towers about calls made by 50,000 anonymous users, the researchers found that most people travel within one to two kilometers of their homes, while a few individuals regularly travel hundreds of kilometers. Those large-scale travelers may be few, but they play a fundamental role when it comes to the spread of many things, including diseases, and are the equivalent of hubs in the network of human mobility, said Barabási, who is also an associate of the Center of Cancer Systems Biology at Harvard University’s Dana Farber Cancer Institute.

In a final example, Barabási showed a network map of the interactions of employees of a Hungarian company with locations in three cities whose senior management was puzzled over how decisions made at the highest levels were consistently and broadly miscommunicated to workers. In that network, the hubs were not senior managers but ordinary workers and low-level managers. Barabási’s research team was able to trace the source of the problem to a single individual. The biggest hub in the network turned out to be a health and environmental manager who had no direct contact with senior management and much contact with a broad spectrum of employees, and who was apparently very adept at spreading misinformation, Barabási said.

CEE’s new DES4 will present speakers from around the world who are pioneers in areas of civil and environmental engineering research and whose talks will be of interest to a wide audience.