An evolutionary method for community detection using a novel local search strategy

Mehdi Moradi and Saeed Parsa

Physica A: Statistical Mechanics and its Applications, 2019, vol. 523, issue C, 457-475

Abstract: Community detection is an NP-hard problem. Therefore, evolutionary-based optimization methods are conventionally applied to cope with the problem. The primary challenge regarding the application of evolutionary-based approaches, specifically to handle large complex networks, is their relatively long execution time. In this respect, this article proposes an extension of a known genetic algorithm, Genetic Algorithm for Community Detection (GACD), for community detection. This new extension is supplied with a novel local search strategy to speed up the convergence and improve the accuracy of the GACD algorithm. To reduce the search space, a locus-based representation of the complex network, in which communities are to be detected, is applied. This type of representation incorporates domain-specific knowledge with the solutions through initialization and reproduction operators. In addition, it does not need to know the number of communities at the beginning of the search process. Our experiments with the real-world and Lancichinetti–Fortunato–Radicchi (LFR) network datasets demonstrate the relatively high capacity of our proposed genetic algorithm in detecting communities with relatively fewer generations and more precision.

Keywords: Community detection; Genetic algorithms; Complex network; Local search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437119301402
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:523:y:2019:i:c:p:457-475

DOI: 10.1016/j.physa.2019.01.133

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 ().