Skip to main content
SpringerLink
Log in

Self-contained algorithms to detect communities in networks

  • Published:
The European Physical Journal B Aims and scope Submit manuscript

Abstract.

The investigation of community structures in networks is an important issue in many domains and disciplines. In this paper we present a new class of local and fast algorithms which incorporate a quantitative definition of community. In this way the algorithms for the identification of the community structure become fully self-contained and one does not need additional non-topological information in order to evaluate the accuracy of the results. The new algorithms are tested on artificial and real-world graphs. In particular we show how the new algorithms apply to a network of scientific collaborations both in the unweighted and in the weighted version. Moreover we discuss the applicability of these algorithms to other non-social networks and we present preliminary results about the detection of community structures in networks of interacting proteins.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. Albert, A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002)

    Article  ADS  Google Scholar 

  2. M.E.J. Newman, SIAM Review 45, 167 (2003)

    Article  ADS  MathSciNet  Google Scholar 

  3. R. Albert, H. Jeong, A.-L. Barabási, Nature 401, 130 (1999)

    Article  ADS  Google Scholar 

  4. A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener, Computer Networks 33, 309 (2000)

    Article  ADS  Google Scholar 

  5. C. Moore, M.E.J. Newman, Phys. Rev. E 61, 5678 (2000)

    Article  ADS  Google Scholar 

  6. R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001)

    Article  ADS  Google Scholar 

  7. H. Jeong, B. Tombor, R. Albert, Z.N. Oltvai, A.-L. Barabási, Nature 407, 651 (2000)

    Article  ADS  Google Scholar 

  8. A. Wagner, D. Fell, Proc. R. Soc. London B 268, 1803 (2001)

    Article  Google Scholar 

  9. E. Ravasz, A. Somera, D.A. Mongru, Z.N. Oltvai, A.-L. Barabási, Science 297, 1551 (2002)

    Article  ADS  Google Scholar 

  10. J.A. Dunne, R.J. Williams, N.D. Martinez, Proc. Natl. Acad. Sci. USA 99, 12917 (2002)

    Article  ADS  Google Scholar 

  11. J. Camacho, R. Guimerá, L.A.N. Amaral, Phys. Rev. Lett. 88, 228102 (2002)

    Article  ADS  Google Scholar 

  12. D. Garlaschelli, G. Caldarelli, L. Pietronero, Nature 423, 165 (2003)

    Article  ADS  Google Scholar 

  13. S. Redner, Eur. Phys. J. B 4, 131 (1998)

    Article  ADS  Google Scholar 

  14. M.E.J. Newman, Proc. Natl. Acad. Sci. USA 98, 404 (2001)

    Article  ADS  MathSciNet  Google Scholar 

  15. P. De Los Rios, Europhys. Lett. 56, 898 (2001)

    Article  ADS  Google Scholar 

  16. A. Rives, T. Galitski, Proc. Natl. Acad. Sci. USA 100, 1128 (2003)

    Article  ADS  Google Scholar 

  17. G.W. Flake, S.R. Lawrence, C.L. Giles, F.M. Coetzee, IEEE Computer 35, 66 (2002)

    Article  Google Scholar 

  18. D. Wilkinson, B.A. Huberman, arXiv:cond-mat/0210147 (2002)

  19. M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026116 (2004)

    Article  ADS  Google Scholar 

  20. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Proc. Natl. Acad. Sci. USA 101, 2658 (2004)

    Article  ADS  Google Scholar 

  21. M.E.J. Newman, arXiv:cond-mat/0309508 (2003)

  22. F. Wu, B.A. Huberman, arXiv:cond-mat/0310600 (2003)

  23. S. Wasserman, K. Faust, Social Network Analysis (Cambridge Univ. Press, Cambridge, U.K., 1994)

  24. M. Girvan, M.E.J. Newman, Proc. Natl. Acad. Sci. USA 99, 7821 (2002)

    Article  ADS  MathSciNet  Google Scholar 

  25. M.E.J. Newman, Phys. Rev. 64, 016131 (2001); U. Brandes, J. Mathematical Sociology 25, 163 (2001)

    ADS  Google Scholar 

  26. H. Zhou, Phys. Rev. E 67, 061901 (2003)

    Article  ADS  Google Scholar 

  27. B. Bollobas, Random Graphs (Academic Press, New York, 1985)

  28. W.W. Zachary, J. Anthrop. Res. 33, 452 (1977)

    Article  Google Scholar 

  29. The comparison between the community structure in the network and the splitting of the club in two groups should be taken with care. While it is reasonable that the break-up pattern is correlated with the preexisting community structure, there is no reason to expect a perfect overlap. Therefore the misclassification of nodes is not an indication of the failure of the detection algorithm

  30. M.E.J. Newman, J. Park, Phys. Rev. E 68, 036122 (2003)

    Article  ADS  Google Scholar 

  31. R. Pastor-Satorras, A. Vásquez, A. Vespignani Phys. Rev. Lett. 87, 258701 (2001)

    Article  ADS  Google Scholar 

  32. Q. Chen, H. Chang, R. Govindn, S. Jamin, S.J. Shenker, W. Willinger, Proceedings of the 21st Annaul Joint Conference of the IEEE Computer and Communications Societies, IEEE Computer Society (2002)

  33. M.E.J. Newman, Phys. Rev. E. 67, 036126 (2003)

    Article  ADS  Google Scholar 

  34. G. Caldarelli, R. Pastor-Satorras, A. Vespignani, arXiv:cond-mat/0212026 (2002)

  35. G. Bianconi, A. Capocci, Phys. Rev. Lett. 90, 078701 (2003)

    Article  ADS  Google Scholar 

  36. I. Xenarios, D.W. Rice, L. Salwinski, M.K. Baron, E.M. Marcotte, D. Eisenberg, Nuclelic Acids Res. 28, 289. The database is available at the web site http://dip.doe-mbi.ucla.edu/ (2000)

    Article  Google Scholar 

  37. S.-H. Yook, Z.N. Oltvai, A.-L. Barabási, Proteomics 4, 928 (2004)

    Article  Google Scholar 

  38. H.W. Mewes, D. Frishman, U. Guldener, G. Mannhaupt, K. Mayer, M. Mokrejs, B. Morgenstern, M. Munsterkotter, S. Rudd, B. Weil, Nucleic Acids Res 30, 31 (2002). The database is available at the web site http://mips.gsf.de/

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Fisica, Universitá di Roma “La Sapienza” and INFM-SMC, Unitá di Roma 1, P.le A. Moro 5, 00185, Roma, Italy

    C. Castellano & V. Loreto

  2. Istituto di Scienze e Tecnologie della Cognizione, C.N.R., Viale Marx, 15, 00137, Roma, Italy

    F. Cecconi & D. Parisi

  3. Dipartimento di Fisica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica 1, 00133, Roma, Italy

    F. Radicchi

Authors
  1. C. Castellano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. Cecconi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. V. Loreto
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. D. Parisi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. F. Radicchi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to V. Loreto.

Additional information

Received: 7 November 2003, Published online: 14 May 2004

PACS:

89.75.Hc Networks and genealogical trees - 87.23.Ge Dynamics of social systems - 87.90. + y Other topics in biological and medical physics

Rights and permissions

Reprints and permissions

About this article

Cite this article

Castellano, C., Cecconi, F., Loreto, V. et al. Self-contained algorithms to detect communities in networks. Eur. Phys. J. B 38, 311–319 (2004). https://doi.org/10.1140/epjb/e2004-00123-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1140/epjb/e2004-00123-0

Keywords

Search

Navigation