|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||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.
|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 Feb 28, 2021
checked on Mar 1, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.