In this paper we propose a new variant of the Variable Neighborhood Decomposition Search (VNDS) heuristic for solving global optimization problems and apply it in detecting clusters in complex community networks. The most used criterion for detecting comunities in networks, despite some recent criticism, is modularity maximization. Experimental results show that the proposed new heuristic outperforms the best algorithms found in the literature.