Research on Complex Networks

The self-similarity of complex networks

Many types of network in nature, society and technology have been found to be 'scale-free', meaning that there is no well-defined average number of links to nodes of the network. Such scale-free structures have been reported in diverse complex systems such as human friendship networks and the networks of scientific collaborations, in the hyperlinks between documents on the World Wide Web, in the pattern of interactions between proteins in living cells, and in the airline links between national airports. Many of these scale-free networks have the familiar 'small-world' property that makes it possible to reach one node from more or less any other in a surprisingly small number of steps (the so-called ``six degrees of separation'') (see [2]).

Our group at City College of New York composed of graduate student Chaoming Song and Prof. Hernan Makse and Prof. Shlomo Havlin from Bar Ilan University now show that complex networks have a more fundamental property: self-similarity [1]. This means that any subsection of the network looks much the same as the whole thing - just as the shape of an individual branch or twig on a tree resembles the whole tree or the self-repeating patterns of the Romanesque brocolis below [2].

Self-similarity is a property of so-called fractal structures, which are approximated by many natural systems, such as coastlines, mountain ranges and river basins. The finding is surprising, because previously scale-free networks were not thought to be self-similar. ``It's a fundamental advance,'' says Albert-Laszlo Barabasi a physicist who study networks at Notre Dame University (see Science News [3]). ``The question of whether complex networks can show such a fractal pattern has been bugging us for a while'', he says.

Our group shows that an essential step of ``coarse-graining'' and renormalizing the complex system, permits the application of statistical mechanics, in a similar fashion as for physical systems undergoing a critical phase transition. These results suggest a common self-organization dynamics of diverse networks into a critical state auguring a new architectural law for complex systems [2]. This new understanding of complex networks has widespread consequences, for example, for protecting the World Wide Web from hacker attacks and for designing drugs with few side effects or unraveling the complicated biological machinery of a cell. Could it be that evolution has evoked a self-organizing principle such that such that it is not only the functionality of the individual molecules that are carefully designed, but the emerging properties on the level of the system as a whole? Our new results poses more question than it answers.

References:

[1] C. Song, S. Havlin, H. A. Makse, `Self-similarity of complex networks', Nature 433, 392-395 (2005).

[2] S. Strogatz, ``Romanesque networks'', Nature News & Views Editorial, 433, 365-366 (2005).

[3] E. Klareich, Science News, January 29, 2005, Vol 167, p. 68, ``Sizing Up Complex Webs: Close or far, many networks look the same''.