Algoritmos evolutivos multiobjetivo para encontrar estructuras de comunidad en redes grandes
Autores: Guerrero, Manuel; Gil, Consolación; Montoya, Francisco G.; Alcayde, Alfredo; Baños, Raúl
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Algoritmos evolutivos multiobjetivo para encontrar estructuras de comunidad en redes grandes
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Sistemas complejos del mundo real
Redes
Detección de comunidades
Algoritmos evolutivos multiobjetivo
Medida de modularidad
Métrica de conductancia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Los sistemas complejos del mundo real suelen ser modelados por redes de tal manera que los elementos son representados por vértices y sus interacciones son representadas por aristas. Una característica importante de estas redes es que contienen grupos de vértices densamente conectados entre sí y conectados de manera más dispersa a nodos fuera del grupo. La detección de comunidades en redes se ha convertido en un área emergente de investigación en años recientes, pero la mayoría de los documentos buscan resolver formulaciones de un solo objetivo, a menudo centradas en la optimización de métricas estructurales, incluida la medida de modularidad. Sin embargo, varios estudios han destacado que considerar un único objetivo a menudo implica límites de resolución e inconvenientes de desequilibrio. Este documento abre una nueva vía de investigación en el estudio de variantes multi-objetivo del problema clásico de detección de comunidades mediante la aplicación de algoritmos evolutivos multi-objetivo que optimizan simultáneamente diferentes objetivos. En particular, se analizaron dos variantes multi-objetivo que involucran no solo la modularidad, sino también la métrica de conductancia y el desequilibrio en el número de nodos de las comunidades. Con este objetivo, se presenta un nuevo algoritmo evolutivo multi-objetivo basado en el conjunto de Pareto que incluye estrategias de inicialización avanzadas y operadores de búsqueda. Los resultados obtenidos al resolver redes a gran escala que representan sistemas de energía de la vida real muestran el buen rendimiento de estos métodos y demuestran que es posible obtener un número equilibrado de nodos en los grupos formados, manteniendo también valores altos de modularidad y conductancia.
Descripción
Los sistemas complejos del mundo real suelen ser modelados por redes de tal manera que los elementos son representados por vértices y sus interacciones son representadas por aristas. Una característica importante de estas redes es que contienen grupos de vértices densamente conectados entre sí y conectados de manera más dispersa a nodos fuera del grupo. La detección de comunidades en redes se ha convertido en un área emergente de investigación en años recientes, pero la mayoría de los documentos buscan resolver formulaciones de un solo objetivo, a menudo centradas en la optimización de métricas estructurales, incluida la medida de modularidad. Sin embargo, varios estudios han destacado que considerar un único objetivo a menudo implica límites de resolución e inconvenientes de desequilibrio. Este documento abre una nueva vía de investigación en el estudio de variantes multi-objetivo del problema clásico de detección de comunidades mediante la aplicación de algoritmos evolutivos multi-objetivo que optimizan simultáneamente diferentes objetivos. En particular, se analizaron dos variantes multi-objetivo que involucran no solo la modularidad, sino también la métrica de conductancia y el desequilibrio en el número de nodos de las comunidades. Con este objetivo, se presenta un nuevo algoritmo evolutivo multi-objetivo basado en el conjunto de Pareto que incluye estrategias de inicialización avanzadas y operadores de búsqueda. Los resultados obtenidos al resolver redes a gran escala que representan sistemas de energía de la vida real muestran el buen rendimiento de estos métodos y demuestran que es posible obtener un número equilibrado de nodos en los grupos formados, manteniendo también valores altos de modularidad y conductancia.