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.

Link communities reveal multiscale complexity in networks

Abstract

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including biological organisms and human society1,2,3. One crucial step when studying the structure and dynamics of networks is to identify communities4,5: groups of related nodes that correspond to functional subunits such as protein complexes6,7 or social spheres8,9,10. Communities in networks often overlap9,10 such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure11,12,13. However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups. Here we reinvent communities as groups of links rather than nodes and show that this unorthodox approach successfully reconciles the antagonistic organizing principles of overlapping communities and hierarchy. In contrast to the existing literature, which has entirely focused on grouping nodes, link communities naturally incorporate overlap while revealing hierarchical organization. We find relevant link communities in many networks, including major biological networks such as protein–protein interaction6,7,14 and metabolic networks11,15,16, and show that a large social network10,17,18 contains hierarchically organized community structures spanning inner-city to regional scales while maintaining pervasive overlap. Our results imply that link communities are fundamental building blocks that reveal overlap and hierarchical organization in networks to be two aspects of the same phenomenon.

This is a preview of subscription content

Access options

Buy article

Get time limited or full article access on ReadCube.

$32.00

All prices are NET prices.

Figure 1: Overlapping communities lead to dense networks and prevent the discovery of a single node hierarchy.
Figure 2: Assessing the relevance of link communities using real-world networks.
Figure 3: Community and membership distributions for the metabolic and mobile phone networks.
Figure 4: Meaningful communities at multiple levels of the link dendrogram.

References

  1. Newman, M. E. J., Barabási, A.-L. & Watts, D. J. The Structure and Dynamics of Networks (Princeton Univ. Press, 2006)

    MATH  Google Scholar 

  2. Caldarelli, G. Scale-Free Networks: Complex Webs in Nature and Technology (Oxford Univ. Press, 2007)

    Book  Google Scholar 

  3. Dorogovtsev, S. N., Goltsev, A. V. & Mendes, J. F. F. Critical phenomena in complex networks. Rev. Mod. Phys. 80, 1275–1335 (2008)

    ADS  Article  Google Scholar 

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

    ADS  MathSciNet  CAS  Article  Google Scholar 

  5. Fortunato, S. Community detection in graphs. Phys. Rep. 486, 75–174 (2010)

    ADS  MathSciNet  Article  Google Scholar 

  6. Krogan, N. J. et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae . Nature 440, 637–643 (2006)

    ADS  CAS  Article  Google Scholar 

  7. Gavin, A.-C. et al. Proteome survey reveals modularity of the yeast cell machinery. Nature 440, 631–636 (2006)

    ADS  CAS  Article  Google Scholar 

  8. Wasserman, S. & Faust, K. Social Network Analysis: Methods and Applications. Structural analysis in the social sciences (Cambridge Univ. Press, 1994)

    Book  Google Scholar 

  9. Palla, G., Derény, I., Farkas, I. & Vicsek, T. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005)

    ADS  CAS  Article  Google Scholar 

  10. Palla, G., Barabási, A. & Vicsek, T. Quantifying social group evolution. Nature 446, 664–667 (2007)

    ADS  CAS  Article  Google Scholar 

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

    ADS  CAS  Article  Google Scholar 

  12. Sales-Pardo, M., Guimera, R., Moreira, A. & Amaral, L. Extracting the hierarchical organization of complex systems. Proc. Natl Acad. Sci. USA 104, 15224–15229 (2007)

    ADS  CAS  Article  Google Scholar 

  13. Clauset, A., Moore, C. & Newman, M. E. J. Hierarchical structure and the prediction of missing links in networks. Nature 453, 98–101 (2008)

    ADS  CAS  Article  Google Scholar 

  14. Yu, H. et al. High-quality binary protein interaction map of the yeast interactome network. Science 322, 104–110 (2008)

    ADS  CAS  Article  Google Scholar 

  15. Guimerà, R. & Amaral, L. A. N. Functional cartography of complex metabolic networks. Nature 433, 895–900 (2005)

    ADS  Article  Google Scholar 

  16. Feist, A. M. et al. A genome-scale metabolic reconstruction for Escherichia coli K-12 MG1655 that accounts for 1260 orfs and thermodynamic information. Mol. Syst. Biol. 3, 121 (2007)

    Article  Google Scholar 

  17. Onnela, J.-P. et al. Structure and tie strengths in mobile communication networks. Proc. Natl Acad. Sci. USA 104, 7332–7336 (2007)

    ADS  CAS  Article  Google Scholar 

  18. González, M. C., Hidalgo, C. A. & Barabási, A.-L. Understanding individual human mobility patterns. Nature 453, 779–782 (2008)

    ADS  Article  Google Scholar 

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

    ADS  CAS  Article  Google Scholar 

  20. Newman, M. E. J. & Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004)

    ADS  CAS  Article  Google Scholar 

  21. Rosvall, M. & Bergstrom, C. T. Maps of random walks on complex networks reveal community structure. Proc. Natl Acad. Sci. USA 105, 1118–1123 (2008)

    ADS  CAS  Article  Google Scholar 

  22. Reichardt, J. & Bornholdt, S. Detecting fuzzy community structures in complex networks with a Potts model. Phys. Rev. Lett. 93, 218701 (2004)

    ADS  Article  Google Scholar 

  23. Li, D. et al. Synchronization interfaces and overlapping communities in complex networks. Phys. Rev. Lett. 101, 168701 (2008)

    ADS  CAS  Article  Google Scholar 

  24. Lancichinetti, A., Fortunato, S. & Kertesz, J. Detecting the overlapping and hierarchical community structure in complex networks. N. J. Phys. 11, 033015 (2009)

    Article  Google Scholar 

  25. Fortunato, S. & Barthélemy, M. Resolution limit in community detection. Proc. Natl Acad. Sci. USA 104, 36–41 (2007)

    ADS  CAS  Article  Google Scholar 

  26. Clauset, A., Newman, M. E. J. & Moore, C. Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)

    ADS  Article  Google Scholar 

  27. Lancichinetti, A. & Fortunato, S. Community detection algorithms: a comparative analysis. Phys. Rev. E 80, 056117 (2009)

    ADS  Article  Google Scholar 

  28. The Gene Ontology Consortium. The Gene Ontology project in 2008. Nucleic Acids Res. 36, D440–D444 (2008)

  29. Evans, T. S. & Lambiotte, R. Line graphs, link partitions and overlapping communities. Phys. Rev. E 80, 016105 (2009)

    ADS  CAS  Article  Google Scholar 

  30. Evans, T. S. & Lambiotte, R. Edge partitions and overlapping communities in complex networks. Preprint at 〈http://arxiv.org/abs/0912.4389〉 (2009)

Download references

Acknowledgements

The authors thank A.-L. Barabási, S. Ahnert, J. Park, D.-S. Lee, P.-J. Kim, N. Blumm, D. Wang, M. A. Yildirim and H. Yu. The authors acknowledge the Center for Complex Network Research, supported by the James S. McDonnell Foundation 21st Century Initiative in Studying Complex Systems; the NSF-DDDAS (CNS-0540348), NSF-ITR (DMR-0426737) and NSF-IIS-0513650 programmes; US ONR Award N00014-07-C; the NIH (U01 A1070499-01/Sub #:111620-2); the DTRA (BRBAA07-J-2-0035); the NS-CTA sponsored by US ARL (W911NF-09-2-0053); and NKTH NAP (KCKHA005). S.L. acknowledges support from the Danish Natural Science Research Council.

Author information

Authors and Affiliations

Authors

Contributions

Y.-Y.A., J.P.B. and S.L. designed and performed the research and wrote the manuscript.

Corresponding author

Correspondence to Sune Lehmann.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Supplementary information

Supplementary Information

This file contains a Supplementary Information (see Table of Contents), Supplementary Figures S1-S32 with legends, Supplementary Tables S1-S2 and References. (PDF 2630 kb)

Supplementary Table 1

This file contains the details for PPI link communities. (ZIP 25 kb)

Supplementary Table 2

This file contains the details for metabolic link communities. (ZIP 12 kb)

Supplementary Table 3

This file contains the details for word association link communities. (ZIP 92 kb)

PowerPoint slides

Rights and permissions

Reprints and Permissions

About this article

Cite this article

Ahn, YY., Bagrow, J. & Lehmann, S. Link communities reveal multiscale complexity in networks. Nature 466, 761–764 (2010). https://doi.org/10.1038/nature09182

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Further reading

Comments

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.

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