Journal Article

Self-similarity of complex networks

Makse, Hernán A., Havlin, Shlomo, Song, Chaoming

2005

Overview

Complex matters ‘Scale-free’ networks, such as linked web pages, people in social groups, or cellular interaction networks show uneven connectivity distributions: there is no typical number of links per node. Many of these networks also exhibit the ‘small-world’ effect, called ‘six degrees of separation’ when applied to sociology. A new analysis of such networks, in which nodes are partitioned into boxes of different sizes, reveals that they share the surprising feature of self-similarity. In other words, these networks are constructed of fractal-like self-repeating patterns or degrees of separation. This may help explain how the scale-free property of such networks arises. Complex networks have been studied extensively owing to their relevance to many real systems such as the world-wide web, the Internet, energy landscapes and biological and social networks 1 , 2 , 3 , 4 , 5 . A large number of real networks are referred to as ‘scale-free’ because they show a power-law distribution of the number of links per node 1 , 6 , 7 . However, it is widely believed that complex networks are not invariant or self-similar under a length-scale transformation. This conclusion originates from the ‘small-world’ property of these networks, which implies that the number of nodes increases exponentially with the ‘diameter’ of the network 8 , 9 , 10 , 11 , rather than the power-law relation expected for a self-similar structure. Here we analyse a variety of real complex networks and find that, on the contrary, they consist of self-repeating patterns on all length scales. This result is achieved by the application of a renormalization procedure that coarse-grains the system into boxes containing nodes within a given ‘size’. We identify a power-law relation between the number of boxes needed to cover the network and the size of the box, defining a finite self-similar exponent. These fundamental properties help to explain the scale-free nature of complex networks and suggest a common self-organization dynamics.

• Publisher: Nature Publishing Group UK,Nature Publishing,Nature Publishing Group
• Subject: Exact sciences and technology / Fractals / Humanities and Social Sciences / letter / Mathematical methods in physics / Mathematics / multidisciplinary / Network management systems / Other topics in mathematical methods in physics / Physics / Science / Science (multidisciplinary)