Exploring Multi-objective Cellular Genetic Algorithms in Community Detection Problems

• Martín Pedemonte ^[1] ; Ángel Panizo-Lledot ^[2] ; Gema Bello-Orgaz ^[2] ; David Camacho ^[2]
  1. [1] Universidad de la República

     Universidad de la República

     Uruguay

     
  2. [2] Universidad Politécnica de Madrid

     Universidad Politécnica de Madrid

     Madrid, España

     
• Localización: Intelligent Data Engineering and Automated Learning – IDEAL 2020. 21st International Conference: Guimarães, Portugal; November 4–6, 2020. Proceedings / Cesar Analide (ed. lit.), Paulo Novais (ed. lit.) , David Camacho Fernández (ed. lit.) , Hujun Yin (ed. lit.), Vol. 2, 2020 (Part II), ISBN 978-3-030-62365-4, págs. 223-235
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • Interest in network analysis has not stopped increasing over the last decade. The Community Detection Problem (CDP) has been a hot topic in network analysis, so many different approaches have been proposed. Among them, optimization methods have proven to be highly effective for this task. Traditionally, the CDP has been tackled as a singleobjective optimization problem. Nevertheless, this trend has started to change, and new methods have appeared following multi-objective approaches. Genetic Algorithms have been applied to the CDP with relative success, especially NSGA-II. However, cellular Genetic Algorithms (cGAs) have yet received little attention. In cGAs, the population is structured in small overlapping neighborhoods producing a slow spread of high-quality solutions. The main contribution of this paper is understanding if the smooth diffusion scheme of MoCell (a multi-objective cGA) can provide any benefit over current multi-objective GAs for the CDP. To verify the effectiveness of MoCell, an evaluation was conducted on 21 synthetically generated networks and two real-world ones. The experiments show that MoCell is able to outperform NSGA-II, especially in large networks scenarios.