Authors: Džamić, Dušan
Aloise, Daniel
Mladenović, Nenad 
Title: Ascent–descent variable neighborhood decomposition search for community detection by modularity maximization
Journal: Annals of Operations Research
Volume: 272
Issue: 1-2
First page: 273
Last page: 287
Issue Date: 1-Jan-2019
Rank: M22
ISSN: 0254-5330
DOI: 10.1007/s10479-017-2553-9
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.
Keywords: Clustering | Community detection | Decomposition | Modularity maximization | Variable neighborhood search
Publisher: Springer Link
Project: CNPq-Brazil Grants 308887/2014-0 and 400350/ 2014-9
Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on May 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.