A fast variable neighborhood search approach for multi-objective Community Detection

Resumen

La detección de comunidades en redes sociales se está convirtiendo en una de las tareas clave en el análisis de redes sociales, ya que ayuda a analizar grupos de usuarios con intereses similares. Esta tarea también es útil en diferentes áreas, como la biología (interacciones de genes y proteínas), la psicología (criterios de diagnóstico) o la criminología (detección de fraude). Este artículo presenta un enfoque metaheurístico basado en Búsqueda de Vecindarios Variables (VNS) que aprovecha la combinación de calidad y diversidad de un procedimiento constructivo inspirado en el Procedimiento de Búsqueda Adaptativa Codiciosa Aleatorizada (GRASP) para detectar comunidades en redes sociales. En este trabajo, el problema de detección de comunidades se modela como un problema de optimización bi-objetivo, donde las dos funciones objetivo a optimizar son la Asociación de Razón Negativa (NRA) y el Corte de Razón (RC), dos objetivos que ya han demostrado estar en conflicto. Para evaluar la calidad de las soluciones obtenidas, utilizamos la métrica de Información Mutua Normalizada (NMI) para las instancias bajo evaluación cuya solución óptima es conocida, y modularidad para aquellas en las que la solución óptima es desconocida. Además, utilizamos métricas ampliamente utilizadas en la comunidad de optimización multi-objetivo para evaluar soluciones, como cobertura, indicador-epsilon, hipervolumen y distancia generacional invertida. Los resultados obtenidos superan al método estado del arte para detección de comunidades sobre un conjunto de instancias de la vida real en ambos aspectos: calidad y tiempo de cómputo.

Citar Esta Publicación

Pérez-Peló, S., Sánchez-Oro, J., Gonzalez-Pardo, A., & Duarte, A. (2021). A fast variable neighborhood search approach for multi-objective community detection. Applied Soft Computing, 112, 107838.