GA-LP: A genetic algorithm based on Label Propagation to detect communities in directed networks

GA-LP: A genetic algorithm based on Label Propagation to detect communities in directed networks

Author Francisquini, Rodrigo Autor UNIFESP Google Scholar
Rosset, Valerio Autor UNIFESP Google Scholar
Nascimento, Maria C. V. Autor UNIFESP Google Scholar
Abstract Many real-world networks have a topological structure characterized by cohesive groups of vertices. To perform the task of identifying such subsets of vertices, community detection in networks has aroused the interest of researchers and practitioners alike. In spite of the existence of various efficient community detection algorithms in the literature, most of them uses global information about the network, not applicable to distributed networks. This paper proposes a genetic-based algorithm to detect communities in directed networks based on local information to generate the offspring. The major difference between the proposed strategy and those found in the literature is the way of exploiting target regions of interest in the solution space. This step is directly influenced by the crossover operator that depends largely on the individual representation. In the introduced strategy, GA-LP, the individual is locally stored in the vertices as labels, what brings more flexibility in the system to be adapted to address applications that involve, for example, dynamic networks. In computational experiments, the proposed strategy showed an outstanding performance, being fast, achieving the best results on average in the networks tested. (C) 2017 Elsevier Ltd. All rights reserved.
Keywords Label Propagation
Genetic algorithm
Community detection problem
xmlui.dri2xhtml.METS-1.0.item-coverage Oxford
Language English
Sponsor Fundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP)
Conselho Nacional de Desenvolvimento em Pequisa (CNPq)
Grant number FAPESP: 2015/21660-4
FAPESP: 2015/18580-9
CNPq: 448614/2014-6
CNPq: 308708/2015-6
Date 2017
Published in Expert Systems With Applications. Oxford, v. 74, p. 127-138, 2017.
ISSN 0957-4174 (Sherpa/Romeo, impact factor)
Publisher Pergamon-Elsevier Science Ltd
Extent 127-138
Access rights Closed access
Type Article
Web of Science ID WOS:000394077500012

Show full item record


File Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)




My Account