Nothing Special   »   [go: up one dir, main page]
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.

  • Letter
  • Published:

Uncovering the overlapping community structure of complex networks in nature and society

Nature volume 435, pages 814–818 (2005)Cite this article

Abstract

Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of1,2,3,4. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins5,6, industrial sectors7 and groups of people8,9) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.

Access through your institution
Buy or subscribe

This is a preview of subscription content, access via your institution

Access options

Access through your institution

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

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

Figure 1: Illustration of the concept of overlapping communities.
Figure 2: The community structure around a particular node in three different networks.
Figure 3: Network of the 82 communities in the DIP core list of the protein–protein interactions of S. cerevisiae for k = 4.
Figure 4: Statistics of the k -clique communities for three large networks.

Similar content being viewed by others

References

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

    Article  ADS  CAS  PubMed  Google Scholar 

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

    Article  ADS  MathSciNet  PubMed  Google Scholar 

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

    Article  ADS  MathSciNet  Google Scholar 

  4. Mendes, J. F. F. & Dorogovtsev, S. N. Evolution of Networks: From Biological Nets to the Internet and WWW. (Oxford Univ. Press, Oxford, 2003)

    MATH  Google Scholar 

  5. Ravasz, E., Somera, A. L., Mongru, D. A., Oltvai, Z. & Barabási, A.-L. Hierarchical organization of modularity in metabolic networks. Science 297, 1551–1555 (2002)

    Article  ADS  CAS  PubMed  Google Scholar 

  6. Spirin, V. & Mirny, L. A. Protein complexes and functional modules in molecular networks. Proc. Natl Acad. Sci. USA 100, 12123–12128 (2003)

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  7. Onnela, J.-P., Chakraborti, A., Kaski, K., Kertész, J. & Kanto, A. Dynamics of market correlations: Taxonomy and portfolio analysis. Phys. Rev. E 68, 056110 (2003)

    Article  ADS  Google Scholar 

  8. Scott, J. Social Network Analysis: A Handbook 2nd edn (Sage, London, 2000)

    Google Scholar 

  9. Watts, D. J., Dodds, P. S. & Newman, M. E. J. Identity and search in social networks. Science 296, 1302–1305 (2002)

    Article  ADS  CAS  PubMed  Google Scholar 

  10. Shiffrin, R. M. & Börner, K. Mapping knowledge domains. Proc. Natl Acad. Sci. USA 101, 5183–5185 (2004)

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  11. Everitt, B. S. Cluster Analysis 3rd edn (Edward Arnold, London, 1993)

    MATH  Google Scholar 

  12. Knudsen, S. A Guide to Analysis of DNA Microarray Data 2nd edn (Wiley-Liss, New York, 2004)

    Book  Google Scholar 

  13. Newman, M. E. J. Detecting community structure in networks. Eur. Phys. J. B 38, 321–330 (2004)

    Article  ADS  CAS  Google Scholar 

  14. Vicsek, T. The bigger picture. Nature 418, 131 (2002)

    Article  ADS  CAS  PubMed  Google Scholar 

  15. Blatt, M., Wiseman, S. & Domany, E. Super-paramagnetic clustering of data. Phys. Rev. Lett. 76, 3251–3254 (1996)

    Article  ADS  CAS  PubMed  Google Scholar 

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

    Article  ADS  MathSciNet  CAS  PubMed  PubMed Central  Google Scholar 

  17. Radicchi, F., Castellano, C., Cecconi, F., Loreto, V. & Parisi, D. Defining and identifying communities in networks. Proc. Natl Acad. Sci. USA 101, 2658–2663 (2004)

    Article  ADS  CAS  PubMed  PubMed Central  Google Scholar 

  18. Newman, M. E. J. Fast algorithm for detecting community structure in networks. Phys. Rev. E 69, 066133 (2004)

    Article  ADS  CAS  Google Scholar 

  19. Faust, K. in Models and Methods in Social Network Analysis (eds Carrington, P., Scott, J. & Wasserman, S.) 117–147 (Cambridge Univ. Press, New York, 2005)

    Book  Google Scholar 

  20. Gavin, A. C. et al. Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 415, 141–147 (2002)

    Article  ADS  CAS  PubMed  Google Scholar 

  21. Everett, M. G. & Borgatti, S. P. Analyzing clique overlap. Connections 21, 49–61 (1998)

    Google Scholar 

  22. Batagelj, V. & Zaversnik, M. Short cycles connectivity. arXiv cs.DS/0308011 http://arxiv.org/abs/cs/0308011 (2003).

  23. Derényi, I., Palla, G. & Vicsek, T. Clique percolation in random networks. Phys. Rev. Lett. 94, 160202 (2005)

    Article  ADS  PubMed  Google Scholar 

  24. Kosub, S. in Network Analysis (eds Brandes, U. & Erlebach, T.) 112–142 (Lecture Notes in Computer Science 3418, Springer, Berlin, 2005)

    Book  Google Scholar 

  25. Warner, S. E-prints and the Open Archives Initiative. Library Hi Tech 21, 151–158 (2003)

    Article  Google Scholar 

  26. Nelson, D. L., McEvoy, C. L. & Schreiber, T. A. The University of South Florida word association, rhyme, and word fragment norms. http://www.usf.edu/freeassociation/.

  27. Xenarios, I. et al. DIP: the Database of Interacting Proteins. Nucleic Acids Res. 28, 289–291 (2000)

    Article  CAS  PubMed  PubMed Central  Google Scholar 

  28. Boyle, E. I. et al. GO:TermFinder—open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes. Bioinformatics 20, 3710–3715 (2004)

    Article  CAS  PubMed  Google Scholar 

  29. Cherry, J. M. et al. Genetic and physical maps of Saccharomyces cerevisiae. Nature 387, 67S–73S (1997)

    Article  Google Scholar 

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

    Article  ADS  CAS  PubMed  Google Scholar 

Download references

Acknowledgements

We thank A.-L. Barabási and P. Pollner for discussions, and B. Kovács and G. Szabó for help with visualization and software support. This research was supported by the Hungarian Research Grant Foundation (OTKA).

Author information

Authors and Affiliations

  1. Biological Physics Research Group of the Hungarian Academy of Sciences, Pázmány P. stny. 1A, H-1117, Budapest, Hungary

    Gergely Palla, Illés Farkas & Tamás Vicsek

  2. Department of Biological Physics, Eötvös University, Pázmány P. stny. 1A, H-1117, Budapest, Hungary

    Gergely Palla, Imre Derényi & Tamás Vicsek

Authors
  1. Gergely Palla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Imre Derényi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Illés Farkas
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tamás Vicsek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tamás Vicsek.

Ethics declarations

Competing interests

Reprints and permissions information is available at npg.nature.com/reprintsandpermissions. The authors declare no competing financial interests.

Supplementary information

Supplementary Notes

Uncovering the overlapping community structure complex networks in nature and society. Also contains additional references. (PDF 285 kb)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Palla, G., Derényi, I., Farkas, I. et al. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005). https://doi.org/10.1038/nature03607

Download citation

  • Received:

  • Accepted:

  • Issue Date:

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

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