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

• DOI: 10.1016/j.physa.2019.01.133
• Publication Date: 2019-02-13T16:49:50Z
• Authors: Mehdi Moradi; Saeed Parsa
• Keywords: Initialization; Representation

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.