A hybrid iterated carousel greedy algorithm for community detection in complex networks

Community detection remains up to this date a challenging combinatorial optimization problem which has received much attention from various scientific fields in recent years. Since the problem for community detection with modularity maximization is known to be NP-complete, many metaheuristics for finding best-possible solutions within an acceptable computational time have been exploited to tackle this problem. In this paper, a hybrid metaheuristic called iterated carousel greedy (ICG) algorithm is presented for solving community detection problem with modularity maximization. The proposed ICG algorithm generates a sequence of solutions by iterating over a greedy construction heuristic using destruction, carousel and reconstruction phases. A local search procedure with strong intensification is applied to search for a better solution in each iteration. Compared with the traditional iterated greedy (IG) metaheuristic, the improved method employs the carousel greedy procedure between destruction and reconstruction to direct the search towards the better solution space. The experimental results on synthetic and real-world networks show the effectiveness and robustness of the proposed method over the existing methods in the literature. (C) 2019 Elsevier B.V. All rights reserved.