Identifying communities in complex networks using learning-based genetic algorithm

Abstract

Identifying communities is one of the hardest tasks in network analysis, and it is critical in various fields, including computer science, biology, sociology, and physics. It aims to partition the graph of a network into groups/clusters of nodes (communities) according to the graph topology. Because determining the optimal partition is a computationally difficult task, it is usually carried out using optimization methods. Most optimization methods proposed for this problem have considered network modularity as the objective function. This article proposes a new evolutionary algorithm called LGA to tackle the community detection problem through modularity optimization. In LGA, learning automata are utilized in the evolution process of the genetic algorithm. Utilizing learning automata in the evolution process of the genetic algorithm largely prevents getting stuck in local optima and premature convergence of the genetic algorithm. It has been tested on different examples of the community detection problem to assess the performance of the LGA. The experiment results showed that the LGA efficiently detects communities within networks. On average, its performance is 26.47% better in real-world networks and 48.32% better in synthetic networks than in compared algorithms.

Keywords

• Network analysis
• Community detection
• Modularity optimization
• Evolutionary algorithm
• Genetic algorithm
• Learning automata