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 s