Abstract
Complex networks from such different fields as biology, technology or sociology share similar organization principles. The possibility of a unique growth mechanism promises to uncover universal origins of collective behaviour. In particular, the emergence of self-similarity in complex networks raises the fundamental question of the growth process according to which these structures evolve. Here we investigate the concept of renormalization as a mechanism for the growth of fractal and non-fractal modular networks. We show that the key principle that gives rise to the fractal architecture of networks is a strong effective ‘repulsion’ (or, disassortativity) between the most connected nodes (that is, the hubs) on all length scales, rendering them very dispersed. More importantly, we show that a robust network comprising functional modules, such as a cellular network, necessitates a fractal topology, suggestive of an evolutionary drive for their existence.
This is a preview of subscription content, access via your institution
Access options
Subscribe to this journal
Receive 12 print issues and online access
$209.00 per year
only $17.42 per issue
Buy this article
- Purchase on Springer Link
- Instant access to full article PDF
Prices may be subject to local taxes which are calculated during checkout
Similar content being viewed by others
References
Mandelbrot, B. B. The Fractal Geometry of Nature (Freeman, San Francisco, 1982).
Vicsek, T. Fractal Growth Phenomena 2nd edn Part IV (World Scientific, Singapore, 1992).
Stanley, H. E. Introduction to Phase Transitions and Critical Phenomena (Oxford Univ. Press, Oxford, 1971).
Song, C., Havlin, S. & Makse, H. A. Self-similarity of complex networks. Nature 433, 392–395 (2005).
Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002).
Pastor-Satorras, R. & Vespignani, A. Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge Univ. Press, Cambridge, 2004).
Strogatz, S. H. Complex systems: Romanesque networks. Nature 433, 365–366 (2005).
Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).
Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).
Hartwell, L. H., Hopfield, L. H., Leibler, S. & Murray, A. W. From molecular to modular cell biology. Nature 402, C47–C52 (1999).
Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. N. & Barabasi, A.-L. Hierarchical organization of modularity in metabolic networks. Science 297, 1551–1555 (2002).
Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl Acad. Sci. 99, 7821–7826 (2002).
Palla, G., Derènyi, I., Farkas, I. & Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005).
Erdös, P. & Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960).
Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).
Cohen, R., Erez, K., ben-Avraham, D. & Havlin, S. Resilience of the internet to random breakdowns. Phys. Rev. Lett. 85, 4626–4628 (2000).
Newman, M. E. J. Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002).
Song, C. & Makse, H. A. Emergence of modularity in the evolution of the yeast protein–protein interaction network. (submitted); preprint at <http://arxiv.org> (2006).
Maslov, S. & Sneppen, K. Specificity and stability in topology of protein networks. Science 296, 910–913 (2002).
Pastor-Satorras, R., Vázquez, A. & Vespegnani, A. Dynamical and correlation properties of the internet. Phys. Rev. Lett. 87, 258701 (2001).
Albert, R., Jeong, H. & Barabási, A.-L. Internet: diameter of the world-wide web. Nature 401, 130–131 (1999).
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The large-scale organization of metabolic networks. Nature 407, 651–654 (2000).
Burch, H. & Cheswick, W. Mapping the internet. IEEE Computer 32, 97–98 (1999).
van Kampen, N. G. Stochastic Processes in Physics and Chemistry (North Holland, Amsterdam, 1981).
Database of Interacting Proteins (DIP); http://dip.doe-mbi.ucla.edu.
Kitano, H. Systems biology: a brief overview. Science 295, 1662–1664 (2002).
Li, L., Alderson, D., Tanaka, R., Doyle, J. C. & Willinger, W. Towards a theory of scale-free graphs: definition, properties, and implications. Preprint at <http://arxiv/abs/cond-mat/0501169> (2005).
Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. F. Pseudofractal scale-free web. Phys. Rev. E 65, 066122 (2002).
Jung, S., Kim, S. & Kahng, B. Geometric fractal growth model for scale-free networks. Phys. Rev. E 65, 056101 (2002).
Acknowledgements
We would like to thank J. Brujić for illuminating discussions and E. Ravasz for providing the data on the metabolic network. S.H. wishes to thank the Israel Science Foundation, ONR and Dysonet for support. This work is supported by the National Science Foundation, DMR-0239504 to H.A.M.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing financial interests.
Supplementary information
Rights and permissions
About this article
Cite this article
Song, C., Havlin, S. & Makse, H. Origins of fractality in the growth of complex networks. Nature Phys 2, 275–281 (2006). https://doi.org/10.1038/nphys266
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1038/nphys266
This article is cited by
-
Age- and Severity-Specific Deep Learning Models for Autism Spectrum Disorder Classification Using Functional Connectivity Measures
Arabian Journal for Science and Engineering (2024)
-
Graph theory analysis reveals an assortative pain network vulnerable to attacks
Scientific Reports (2023)
-
Visibility graph analysis of the sea surface temperature irreversibility during El Niño events
Nonlinear Dynamics (2023)
-
Towards a better understanding of the characteristics of fractal networks
Applied Network Science (2023)
-
Detecting the ultra low dimensionality of real networks
Nature Communications (2022)