Skip to main content
Log in

A smart local moving algorithm for large-scale modularity-based community detection

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

Abstract

We introduce a new algorithm for modularity-based community detection in large networks. The algorithm, which we refer to as a smart local moving algorithm, takes advantage of a well-known local moving heuristic that is also used by other algorithms. Compared with these other algorithms, our proposed algorithm uses the local moving heuristic in a more sophisticated way. Based on an analysis of a diverse set of networks, we show that our smart local moving algorithm identifies community structures with higher modularity values than other algorithms for large-scale modularity optimization, among which the popular “Louvain algorithm”. The computational efficiency of our algorithm makes it possible to perform community detection in networks with tens of millions of nodes and hundreds of millions of edges. Our smart local moving algorithm also performs well in small and medium-sized networks. In short computing times, it identifies community structures with modularity values equally high as, or almost as high as, the highest values reported in the literature, and sometimes even higher than the highest values found in the literature.

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

Access this article

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. S. Fortunato, Phys. Rep. 486, 75 (2010)

    Article  MathSciNet  ADS  Google Scholar 

  2. M.E.J. Newman, M. Girvan, Phys. Rev. E 69, 026113 (2004)

    Article  ADS  Google Scholar 

  3. M.E.J. Newman, Phys. Rev. E 69, 066133 (2004)

    Article  ADS  Google Scholar 

  4. M.E.J. Newman, Phys. Rev. E 70, 056131 (2004)

    Article  ADS  Google Scholar 

  5. E.A. Leicht, M.E.J. Newman, Phys. Rev. Lett. 100, 118703 (2008)

    Article  ADS  Google Scholar 

  6. J. Reichardt, S. Bornholdt, Phys. Rev. E 74, 016110 (2006)

    Article  MathSciNet  ADS  Google Scholar 

  7. S. Fortunato, M. Barthélemy, Proc. Natl. Acad. Sci. USA 104, 36 (2007)

    Article  ADS  Google Scholar 

  8. L. Waltman, N.J. van Eck, E.C.M. Noyons, J. Informetr. 4, 629 (2010)

    Article  Google Scholar 

  9. V.A. Traag, P. van Dooren, Y. Nesterov, Phys. Rev. E 84, 016114 (2011)

    Article  ADS  Google Scholar 

  10. U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, D. Wagner, IEEE Trans. Knowl. Data Eng. 20, 172 (2008)

    Article  Google Scholar 

  11. G. Xu, S. Tsoka, L.G. Papageorgiou, Eur. Phys. J. B 60, 231 (2007)

    Article  MATH  ADS  Google Scholar 

  12. D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, S. Perron, L. Liberti, Phys. Rev. E 82, 046112 (2010)

    Article  ADS  Google Scholar 

  13. A. Clauset, M.E.J. Newman, C. Moore, Phys. Rev. E 70, 066111 (2004)

    Article  ADS  Google Scholar 

  14. R. Guimerà, M. Sales-Pardo, L.A.N. Amaral, Phys. Rev. E 70, 025101 (2004)

    Article  ADS  Google Scholar 

  15. J. Duch, A. Arenas, Phys. Rev. E 72, 027104 (2005)

    Article  ADS  Google Scholar 

  16. M.E.J. Newman, Phys. Rev. E 74, 036104 (2006)

    Article  MathSciNet  ADS  Google Scholar 

  17. M.E.J. Newman, Proc. Natl. Acad. Sci. USA 103, 8577 (2006)

    Article  ADS  Google Scholar 

  18. S. Lehmann, L.K. Hansen, Eur. Phys. J. B 60, 83 (2007)

    Article  ADS  Google Scholar 

  19. J. Lee, S.P. Gross, J. Lee, Phys. Rev. E 85, 056702 (2012)

    Article  ADS  Google Scholar 

  20. V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre, J. Stat. Mech. Theor. Exp. 10, P10008 (2008)

    Article  Google Scholar 

  21. R. Rotta, A. Noack, J. Exp. Algorithmics 16, 2.3 (2011)

    Article  MathSciNet  Google Scholar 

  22. W.W. Zachary, J. Anthr. Res. 33, 452 (1977)

    Google Scholar 

  23. P. Schuetz, A. Caflisch, Phys. Rev. E 77, 046112 (2008)

    Article  ADS  Google Scholar 

  24. Z. Ye, S. Hu, J. Yu, Phys. Rev. E 78, 046115 (2008)

    Article  MathSciNet  ADS  Google Scholar 

  25. M.J. Barber, J.W. Clark, Phys. Rev. E 80, 026129 (2009)

    Article  ADS  Google Scholar 

  26. J. Mei, S. He, G. Shi, Z. Wang, W. Li, New J. Phys. 11, 043025 (2009)

    Article  ADS  Google Scholar 

  27. X. Liu, T. Murata, Physica A 389, 1493 (2010)

    Article  ADS  Google Scholar 

  28. A. Arenas, J. Duch, A. Fernández, S. Gómez, New J. Phys. 9, 176 (2007)

    Article  ADS  Google Scholar 

  29. J. Yang, J. Leskovec, in Proceedings of the 12th IEEE Int. Conf. Data Min., Brussels, 2012, p. 745

  30. A.-L. Barabási, R. Albert, Science 286, 509 (1999)

    Article  MathSciNet  ADS  Google Scholar 

  31. L. Waltman, N.J. van Eck, J. Am. Soc. Inf. Sci. Technol. 63, 2378 (2012)

    Article  Google Scholar 

  32. P. Boldi, B. Codenotti, M. Santini, S. Vigna, Softw. Pract. Exp. 34, 711 (2004)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Ludo Waltman.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Waltman, L., van Eck, N.J. A smart local moving algorithm for large-scale modularity-based community detection. Eur. Phys. J. B 86, 471 (2013). https://doi.org/10.1140/epjb/e2013-40829-0

Download citation

  • Received:

  • Revised:

  • Published:

  • DOI: https://doi.org/10.1140/epjb/e2013-40829-0

Keywords

Navigation