NGA-LP: A robust and improved genetic algorithm to detect communities in directed networks

Autor(es)

Francisquini, Rodrigo ; Nascimento, Maria C. V. ; Basgalupp, Marcio P. ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2018-01-01.

Resumo

Understanding the community structure of real-world networks is an important task to predict the dynamics of many complex systems. To this end, several optimization methods were developed to maximize the widely studied measure known as Modularity. Most of these methods use global information and, therefore, are computationally expensive to process large-scale networks. This paper proposes a genetic algorithm to detect communities in directed networks, named NGA-LP, that contains local genetic operators designed to have low computational cost. The primary advantage of NGA-LP is the local representation, where the vertices store the information of the individuals. This representation makes possible the use of local genetic operators which do not require global information. Moreover, NGA-LP combines a pair of crossover operators that are automatically chosen according to the characteristics of the network, guided by the quality of the solution. The goal of combining different crossover operators is to ensure the robustness and capability of handling with different networks in an adaptive fashion. In the computational tests carried out in this paper, the introduced algorithm achieved excellent results and outperformed the other benchmark algorithms, even for undirected networks. (AU)

• Processo FAPESP: 16/02870-0 - Hiper-heurísticas multi-objetivas para construção automática de algoritmos de indução de árvores de decisão com múltiplos testes
• Beneficiário: Márcio Porto Basgalupp
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 15/21660-4 - Hibridização de métodos heurísticos e exatos para abordar problemas de otimização combinatória
• Beneficiário: Mariá Cristina Vasconcelos Nascimento Rosset
• Modalidade de apoio: Auxílio à Pesquisa - Regular