Erica Klarreich

Researchers have discovered that a remarkable diversity of complex networks, including the World Wide Web and patterns in cellular biochemistry, have a common architecture with snowflakes and trees. These networks all display similar patterns, whether viewed from up close or far away.

FRACTAL BURST. In the World Wide Web, links between individual nodes follow patterns similar to those of links between clusters of nodes, between clusters of clusters, and so on. Makse

"It's a fundamental advance," says Albert-László Barabási, a physicist who studies networks at the University of Notre Dame in Indiana. The question of whether complex networks can show such a fractal pattern, also known as self-similarity, "has been bugging us for a while," he says.

In recent years, researchers have found that a surprising range of networks has a common structure: a few major hubs with many connections and many minor nodes with only a few connections. In the World Wide Web, for instance, tens of thousands of sites link to a few popular Web sites, such as Google and Yahoo, while there are often just a few links to an individual's home page.

Now, in a surprising finding, researchers have identified self-similarity in four types of complex networks: the World Wide Web, a network of actors who have been in films together, networks of proteins with links between those that can bind to each other, and networks of other cellular molecules with links between molecules involved in the same biochemical reactions.

The researchers note that they discovered this wide-ranging characteristic by figuring out how to "zoom out" and look at networks from farther and farther away. They started by using computer analysis to cover each network with non-overlapping boxes, each of which contained a cluster of nodes separated by less than a specified number of links. Next, the investigators essentially blurred their vision, paying attention to how the boxes—rather than the individual nodes—were connected.

By repeating this procedure many times, the researchers could observe the structure of a network on many levels. In the Jan. 27 Nature, Hernán Makse of the City College of New York and his coworkers report that all the blurred networks have connectivity patterns similar to those of the original network.

Ordinarily, Barabási says, objects with fractal structures fit into a finite-dimensional space, such as a flat plane or a three-dimensional space. By contrast, mathematicians have modeled complex networks such as the World Wide Web as infinite dimensional because there's no realistic way to fit such a network, with hubs having so many links, into a finite-dimensional space. This property led Barabási and many other researchers to assume that complex networks cannot be self-similar.

"If you had asked me yesterday, I would have said they are surely not self-similar," Barabási says.

Understanding the architecture of complex networks is important, for example, for protecting the World Wide Web from hacker attacks and for designing drugs with few side effects, Barabási says. However, the contribution of the new finding to those advances isn't yet clear, he says.

"They've found something new here, but we don't know yet whether it is a Rosetta stone that will let us translate the mysteries of networks into something we understand," says Steven Strogatz, a mathematician at Cornell University.

References:

Song, C., S. Havlin, and H.A. Makse. 2005. Self-similarity of complex networks. Nature 433(Jan. 27):392-395.

Further Readings:

Barabási, A.-L., and E. Bonabeau. 2003. Scale-free networks. Scientific American 288(May):60-69.

Strogatz, S.H. 2005. Complex systems: Romanesque networks. Nature 433(Jan. 27):365-366.

Sources:

Albert-László Barabási
Department of Physics
University of Notre Dame
Notre Dame, IN, 46556

Hernán Makse
Levich Institute and Physics Department
City College of New York
New York, NY 10031

Steven Strogatz
Department of Theoretical and Applied Mechanics
Cornell University
Ithaca, NY 14853