Ascent–descent variable neighborhood decomposition search for community detection by modularity maximization

Abstract

In this paper we propose a new variant of the Variable Neighborhood Decomposition Search (VNDS) heuristic for solving global optimization problems. We call it Ascent-Descent VNDS since it performs “boundary effect”, or local search step, even if the improvement in solving the subproblem has not been obtained. We apply it in detecting communities in large networks by modularity maximization, the criterion which is, despite of some recent criticism, most widely used. Computational analysis is performed on 22 instances from the 10th DIMACS Implementation Challenge. On 13 instances where optimal solutions were not known, we got the improved best known solutions on 9 instances and on 4 instances the solution was equal to the best known. Thus, the proposed new heuristic outperforms the current state-of-the-art algorithms from the literature.