Close or Far, Fractal Networks Look The Same

By Roland Piquepaille

Many complex networks, from the Internet to proteins interacting with other ones in a cell, or from actors having played together to Romanesque broccoli, have "a common architecture with snowflakes and trees." And even more surprisingly, Science News reports that "these networks all display similar patterns, whether viewed from up close or far away." In fact, all these networks are scale-free networks. Like the airline system, they contain hubs -- nodes with a very high number of links. In such networks, the distribution of node linkages follows a power law in that most nodes have just a few connections and some have a tremendous number of links. In that sense, the system has no "scale." The fact that these complex networks can show such a fractal pattern has important implications for a host of applications, from drug development to Internet security. Read more...

Here are some short excerpts from the Science News article.

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.

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.

Here are two examples of representations of complex networks.

The Internet is a scale-free network in that some sites have a seemingly unlimited number of connections to other sites. This map, made on February 6, 2003, traces the shortest routes from a test Web site to about 100,000 others, using like colors for similar Web addresses. (Image credit: Internet Mapping Project of Lumeta Corporation; Legend credit: Scientific American)

And this map of interacting proteins in yeast highlights the discovery that highly linked, or hub, proteins tend to be crucial for a cell's survival. Red denotes essential proteins (their removal will cause the cell to die). Orange represents proteins of some importance (their removal will slow cell growth). Green and yellow represent proteins of lesser or unknown significance, respectively. (Credit for image and legend: Scientific American).

Now, where can lead this discovery of this fractal property of complex networks?

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, says Albert-László Barabási, a physicist who studies networks at the University of Notre Dame in Indiana. 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.

For more information, Barabási has published many articles on these complex networks. The images above come from an article he wrote with Eric Bonabeau, Chairman and Chief Scientific Officer of Icosystem, a consulting firm based in Cambridge, Mass., and published by Scientific American in its May 2003 issue, "Scale-Free Networks."

Here is a link to the abstract which states that "scientists have recently discovered that various complex systems have an underlying architecture governed by shared organizing principles. This insight has important implications for a host of applications, from drug development to Internet security."

And here is a link to the full paper if you have more time (PDF format, 10 pages, 9.34 MB).

And Strogatz, mentioned above, wrote "Romanesque networks" for Nature which was published on January 27, 2005. In this article, Strogatz explores the exquisitely symmetrical properties of the Romanesque broccoli, which he called a "fractal vegetable."

Sources: Erica Klarreich, Science News, Vol. 167, No. 5, Page 68, January 29, 2005; and various other websites

Related stories can be found in the following categories.

• Internet
  
• Networking
  
• Security
  
• Social Networks