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

Author(s)

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

• Document type: Journal article
• Source: 2018 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC); v. N/A, p. 8-pg., 2018-01-01.

Abstract

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)

• FAPESP's process: 16/02870-0 - Multi-objective hyper-heuristics for automatic design of multi-test decision tree induction algorithms
• Grantee: Márcio Porto Basgalupp
• Support Opportunities: Regular Research Grants
• FAPESP's process: 15/21660-4 - Hibridizing heuristic and exact methods to approach combinatorial optimization problems
• Grantee: Mariá Cristina Vasconcelos Nascimento Rosset
• Support Opportunities: Regular Research Grants