- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Free to Read
  • Access by Xinjiang University

Near linear time algorithm to detect community structures in large-scale networks

Usha Nandini Raghavan1, Réka Albert2, and Soundar Kumara1

  • 1Department of Industrial Engineering, The Pennsylvania State University, University Park, Pennsylvania 16802, USA
  • 2Department of Physics, The Pennsylvania State University, University Park, Pennsylvania 16802, USA

PDF

Phys. Rev. E 76, 036106 – Published 11 September, 2007

DOI: https://doi.org/10.1103/PhysRevE.76.036106

Abstract

Community detection and analysis is an important methodology for understanding the organization of various real-world networks and has applications in problems as diverse as consensus formation in social communities or the identification of functional modules in biochemical networks. Currently used algorithms that identify the community structures in large-scale real-world networks require a priori information such as the number and sizes of communities or are computationally expensive. In this paper we investigate a simple label propagation algorithm that uses the network structure alone as its guide and requires neither optimization of a predefined objective function nor prior information about the communities. In our algorithm every node is initialized with a unique label and at every step each node adopts the label that most of its neighbors currently have. In this iterative process densely connected groups of nodes form a consensus on a unique label to form communities. We validate the algorithm by applying it to networks whose community structures are known. We also demonstrate that the algorithm takes an almost linear time and hence it is computationally less expensive than what was possible so far.

View figure in article

Collections

This article appears in the following collection:

Physical Review E 25th Anniversary Milestones

The year 2018 marks the 25th anniversary of Physical Review E. To celebrate the journal’s rich legacy, during the upcoming year we highlight a series of papers that made important contributions to their field. These milestone articles were nominated by members of the Editorial Board of Physical Review E, in collaboration with the journal’s editors. The 25 milestone articles, including an article for each calendar year from 1993 through 2017 and spanning all major subject areas of the journal, will be unveiled in chronological order and will be featured on the journal website.

Article Text

References (38)

  1. R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002).
  2. R. Albert, H. Jeong, and A.-L. Barabási, Nature (London) 401, 130 (1999).
  3. A.-L. Barabási and R. Albert, Science 286, 509 (1999).
  4. M. Newman, SIAM (Soc. Ind. Appl. Math.) Rev. 45, 167 (2003).
  5. M. Girvan and M. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002).
  6. S. Wasserman and K. Faust, Social Network Analysis (Cambridge University Press, Cambridge, England, 1994).
  7. L. Danon, A. Díaz-Guilera, and A. Arenas, J. Stat. Mech.: Theor. Exp. 2006 P11010 (2006).
  8. J. Eckmann and E. Moses, Proc. Natl. Acad. Sci. U.S.A. 99, 5825 (2002).
  9. G. Flake, S. Lawrence, and C. Giles, Proceedings of the 6th ACM SIGKDD, 2000, pp. 150–160.
  10. R. Guimerà and L. Amaral, Nature (London) 433, 895 (2005).
  11. M. Gustafsson, M. Hornquist, and A. Lombardi, Physica A 367, 559 (2006).
  12. M. B. Hastings, Phys. Rev. E 74, 035102(R) (2006).
  13. M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
  14. G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Nature (London) 435, 814 (2005).
  15. F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Proc. Natl. Acad. Sci. U.S.A. 101, 2658 (2004).
  16. D. Karger, J. ACM 47, 46 (2000).
  17. B. Kernighan and S. Lin, Bell Syst. Tech. J. 29, 291 (1970).
  18. C. Fiduccia and R. Mattheyses, Proceedings of the 19th Annual ACM IEEE Design Automation Conference, 1982, pp. 175–181.
  19. B. Hendrickson and R. Leland, SIAM (Soc. Ind. Appl. Math.) J. Sci. Comput. 16, 452 (1995).
  20. M. Stoer and F. Wagner, J. ACM 44, 585 (1997).
  21. C. Thompson, Proceedings of the 11th Annual ACM Symposium on Theory of Computing, 1979, pp. 81–88.
  22. M. E. J.Newman, Phys. Rev. E 69, 066133 (2004).
  23. P. Pons and M. Latapy, e-print arXiv:physics/0512106.
  24. J. Duch and A. Arenas, Phys. Rev. E 72, 027104 (2005).
  25. M. E. J. Newman, Phys. Rev. E 74, 036104 (2006).
  26. F. Wu and B. Huberman, Eur. Phys. J. B 38, 331 (2004).
  27. J. P. Bagrow and E. Bollt, Phys. Rev. E 72, 046108 (2005).
  28. L. Costa, e-print arXiv:cond-mat/0405022.
  29. M. E. J. Newman, Eur. Phys. J. B 38, 321 (2004).
  30. A. Clauset, M. E. J. Newman, and C. Moore, Phys. Rev. E 70, 066111 (2004).
  31. B. Bollobás, Random Graphs (Academic Press, Orlando, FL, 1985).
  32. W. Zachary, J. Anthropol. Res. 33, 452 (1977).
  33. M. Newman, Proc. Natl. Acad. Sci. U.S.A. 98, 404 (2001).
  34. H. Jeong, S. Mason, A.-L. Barabási, and Z. Oltvai, Nature (London) 411, 41 (2001).
  35. G. Milligan and D. Schilling, Multivariate Behav. Res. 20, 97 (1985).
  36. D. Gfeller, J. C. Chappelier, and P. De Los Rios, Phys. Rev. E 72, 056135 (2005).
  37. D. Wilkinson and B. Huberman, Proc. Natl. Acad. Sci. U.S.A. 101, 5241 (2004).
  38. A. Arenas, L. Danon, A. Díaz-Guilera, P. Gleiser, and R. Guimerà, Eur. Phys. J. B 38, 373 (2004).

Outline

Information

Phys. Rev. E 76, 036106– Published 11 September, 2007
  • Received 9 April 2007

© 2007 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation