Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Article
  • Published:

Origins of fractality in the growth of complex networks

Nature Physics volume 2, pages 275–281 (2006)Cite this article

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

Buy this article

  • Purchase on Springer Link
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Figure 1: Self-similar dynamical evolution of networks.
Figure 2: Empirical results on real complex networks.
Figure 3: Predictions of the renormalization growth mechanism of complex networks.
Figure 4: Practical implications of the renormalization growth approach and fractality.

Similar content being viewed by others

References

  1. Mandelbrot, B. B. The Fractal Geometry of Nature (Freeman, San Francisco, 1982).

    MATH  Google Scholar 

  2. Vicsek, T. Fractal Growth Phenomena 2nd edn Part IV (World Scientific, Singapore, 1992).

    Book  Google Scholar 

  3. Stanley, H. E. Introduction to Phase Transitions and Critical Phenomena (Oxford Univ. Press, Oxford, 1971).

    Google Scholar 

  4. Song, C., Havlin, S. & Makse, H. A. Self-similarity of complex networks. Nature 433, 392–395 (2005).

    Article  ADS  Google Scholar 

  5. Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002).

    Article  ADS  MathSciNet  Google Scholar 

  6. Pastor-Satorras, R. & Vespignani, A. Evolution and Structure of the Internet: A Statistical Physics Approach (Cambridge Univ. Press, Cambridge, 2004).

    Book  Google Scholar 

  7. Strogatz, S. H. Complex systems: Romanesque networks. Nature 433, 365–366 (2005).

    Article  ADS  Google Scholar 

  8. Watts, D. J. & Strogatz, S. H. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998).

    Article  ADS  Google Scholar 

  9. Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999).

    Article  ADS  MathSciNet  Google Scholar 

  10. Hartwell, L. H., Hopfield, L. H., Leibler, S. & Murray, A. W. From molecular to modular cell biology. Nature 402, C47–C52 (1999).

    Article  Google Scholar 

  11. 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).

    Article  ADS  Google Scholar 

  12. Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl Acad. Sci. 99, 7821–7826 (2002).

    Article  ADS  MathSciNet  Google Scholar 

  13. 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).

    Article  ADS  Google Scholar 

  14. Erdös, P. & Rényi, A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960).

    MathSciNet  MATH  Google Scholar 

  15. Albert, R., Jeong, H. & Barabási, A.-L. Error and attack tolerance of complex networks. Nature 406, 378–382 (2000).

    Article  ADS  Google Scholar 

  16. Cohen, R., Erez, K., ben-Avraham, D. & Havlin, S. Resilience of the internet to random breakdowns. Phys. Rev. Lett. 85, 4626–4628 (2000).

    Article  ADS  Google Scholar 

  17. Newman, M. E. J. Assortative mixing in networks. Phys. Rev. Lett. 89, 208701 (2002).

    Article  ADS  Google Scholar 

  18. 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).

  19. Maslov, S. & Sneppen, K. Specificity and stability in topology of protein networks. Science 296, 910–913 (2002).

    Article  ADS  Google Scholar 

  20. Pastor-Satorras, R., Vázquez, A. & Vespegnani, A. Dynamical and correlation properties of the internet. Phys. Rev. Lett. 87, 258701 (2001).

    Article  ADS  Google Scholar 

  21. Albert, R., Jeong, H. & Barabási, A.-L. Internet: diameter of the world-wide web. Nature 401, 130–131 (1999).

    Article  ADS  Google Scholar 

  22. 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).

    Article  ADS  Google Scholar 

  23. Burch, H. & Cheswick, W. Mapping the internet. IEEE Computer 32, 97–98 (1999).

    Article  Google Scholar 

  24. van Kampen, N. G. Stochastic Processes in Physics and Chemistry (North Holland, Amsterdam, 1981).

    MATH  Google Scholar 

  25. Database of Interacting Proteins (DIP); http://dip.doe-mbi.ucla.edu.

  26. Kitano, H. Systems biology: a brief overview. Science 295, 1662–1664 (2002).

    Article  ADS  Google Scholar 

  27. 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).

  28. Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. F. Pseudofractal scale-free web. Phys. Rev. E 65, 066122 (2002).

    Article  ADS  Google Scholar 

  29. Jung, S., Kim, S. & Kahng, B. Geometric fractal growth model for scale-free networks. Phys. Rev. E 65, 056101 (2002).

    Article  ADS  Google Scholar 

Download references

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

  1. Levich Institute and Physics Department, City College of New York, New York, New York, 10031, USA

    Chaoming Song & Hernán A. Makse

  2. Minerva Center and Department of Physics, Bar-Ilan University, Ramat Gan, 52900, Israel

    Shlomo Havlin

Authors
  1. Chaoming Song
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shlomo Havlin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hernán A. Makse
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hernán A. Makse.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Supplementary information

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/nphys266

This article is cited by

Search

Advanced search

Quick links

Nature Briefing

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing