Aproximándose a la solución óptima del problema de la comunidad local de la máxima -cuasi-clique
Autores: Conde-Cespedes, Patricia
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Aproximándose a la solución óptima del problema de la comunidad local de la máxima -cuasi-clique
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería Eléctrica y Electrónica
Palabras clave
Análisis de redes complejas
Detección de comunidades
Detección de comunidades locales
Alta densidad
Cuasiclústeres
NP-duro
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
El análisis de redes complejas (CNA) ha atraído mucha atención en los últimos años. Una tarea interesante en el análisis de redes complejas de CNA es la detección de comunidades. En este documento, nos enfocamos en la Detección de Comunidades Locales, que es el problema de detectar la comunidad de un nodo dado de interés en toda la red. Además, estudiamos el problema de encontrar comunidades locales de alta densidad, conocidas en teoría de grafos (para valores altos de en el intervalo ]0,1[). Desafortunadamente, cuanto mayor es, más pequeñas se vuelven las comunidades. Esto llevó al problema de encontrar comunidades locales que son -cuasiclásicos de tamaño máximo. Este problema es NP-duro, por lo tanto, para acercarse a la solución óptima, existen algunas heurísticas. Cuando es alto (>0.5) el diámetro de un -cuasiclásico máximo es a lo sumo 2. Basándonos en esta propiedad, proponemos un algoritmo para calcular un límite superior para acercarse a la solución óptima. Evaluamos nuestro método en redes reales y concluimos que, en la mayoría de los casos, el límite es muy preciso. Además, para una red pequeña real, el valor óptimo se logra exactamente en más del 80% de los casos.
Descripción
El análisis de redes complejas (CNA) ha atraído mucha atención en los últimos años. Una tarea interesante en el análisis de redes complejas de CNA es la detección de comunidades. En este documento, nos enfocamos en la Detección de Comunidades Locales, que es el problema de detectar la comunidad de un nodo dado de interés en toda la red. Además, estudiamos el problema de encontrar comunidades locales de alta densidad, conocidas en teoría de grafos (para valores altos de en el intervalo ]0,1[). Desafortunadamente, cuanto mayor es, más pequeñas se vuelven las comunidades. Esto llevó al problema de encontrar comunidades locales que son -cuasiclásicos de tamaño máximo. Este problema es NP-duro, por lo tanto, para acercarse a la solución óptima, existen algunas heurísticas. Cuando es alto (>0.5) el diámetro de un -cuasiclásico máximo es a lo sumo 2. Basándonos en esta propiedad, proponemos un algoritmo para calcular un límite superior para acercarse a la solución óptima. Evaluamos nuestro método en redes reales y concluimos que, en la mayoría de los casos, el límite es muy preciso. Además, para una red pequeña real, el valor óptimo se logra exactamente en más del 80% de los casos.