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

Dušan Džamić (), Daniel Aloise () and Nenad Mladenović ()
Additional contact information
Dušan Džamić: University of Belgrade
Daniel Aloise: Universidade Federal do Rio Grande do Norte
Nenad Mladenović: Serbian Academy of Sciences

Annals of Operations Research, 2019, vol. 272, issue 1, No 13, 273-287

Abstract: 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; Modularity maximization; Variable neighborhood search; Decomposition (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2553-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:272:y:2019:i:1:d:10.1007_s10479-017-2553-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2553-9

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().