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.

• Received 27 April 2009

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