logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro