A hybrid iterated carousel greedy algorithm for community detection in complex networks

Hanzhang Kong, Qinma Kang, Wenquan Li, Chao Liu, Yunfan Kang and Hong He

Physica A: Statistical Mechanics and its Applications, 2019, vol. 536, issue C

Abstract: Community detection remains up to this date a challenging combinatorial optimization problem which has received much attention from various scientific fields in recent years. Since the problem for community detection with modularity maximization is known to be NP-complete, many metaheuristics for finding best-possible solutions within an acceptable computational time have been exploited to tackle this problem. In this paper, a hybrid metaheuristic called iterated carousel greedy (ICG) algorithm is presented for solving community detection problem with modularity maximization. The proposed ICG algorithm generates a sequence of solutions by iterating over a greedy construction heuristic using destruction, carousel and reconstruction phases. A local search procedure with strong intensification is applied to search for a better solution in each iteration. Compared with the traditional iterated greedy (IG) metaheuristic, the improved method employs the carousel greedy procedure between destruction and reconstruction to direct the search towards the better solution space. The experimental results on synthetic and real-world networks show the effectiveness and robustness of the proposed method over the existing methods in the literature.

Keywords: Iterated greedy heuristic; Carousel greedy; Community detection; Modularity maximization (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037843711931235X
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

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:eee:phsmap:v:536:y:2019:i:c:s037843711931235x

DOI: 10.1016/j.physa.2019.122124

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().