Detección local de comunidades basada en pequeños cliques
Autores: Hamann, Michael; Röhrs, Eike; Wagner, Dorothea
Idioma: Inglés
Editor: MDPI
Año: 2017
Acceso abierto
Artículo científico
2017
Detección local de comunidades basada en pequeños cliques
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Detección de comunidades
Subgrafos densos
Detección de comunidades locales
Redes ponderadas
Algoritmos de detección de comunidades superpuestas
Nodo semilla
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 36
Citaciones: Sin citaciones
La detección de comunidades tiene como objetivo encontrar subgrafos densos en una red. Consideramos el problema de encontrar una comunidad localmente alrededor de un nodo semilla tanto en redes no ponderadas como ponderadas. Esta es una alternativa más rápida a los algoritmos que detectan comunidades que cubren toda la red cuando en realidad solo se necesita una comunidad única. Además, muchos algoritmos de detección de comunidades superpuestas utilizan algoritmos de detección de comunidades locales como bloque de construcción básico. Proporcionamos una amplia comparación de diferentes estrategias existentes para expandir un nodo semilla de forma ávida en una comunidad. Para esto, realizamos una evaluación experimental extensa tanto en grafos de referencia sintéticos como en redes del mundo real. Mostramos que los resultados tanto en redes sintéticas como en redes del mundo real pueden mejorarse significativamente comenzando desde el cliqué más grande en el vecindario del nodo semilla. Además, nuestros experimentos indican que los algoritmos que utilizan puntuaciones basadas en triángulos superan a otros algoritmos en la mayoría de los casos. Proporcionamos descripciones teóricas, así como implementaciones de código abierto de todos los algoritmos utilizados.
Descripción
La detección de comunidades tiene como objetivo encontrar subgrafos densos en una red. Consideramos el problema de encontrar una comunidad localmente alrededor de un nodo semilla tanto en redes no ponderadas como ponderadas. Esta es una alternativa más rápida a los algoritmos que detectan comunidades que cubren toda la red cuando en realidad solo se necesita una comunidad única. Además, muchos algoritmos de detección de comunidades superpuestas utilizan algoritmos de detección de comunidades locales como bloque de construcción básico. Proporcionamos una amplia comparación de diferentes estrategias existentes para expandir un nodo semilla de forma ávida en una comunidad. Para esto, realizamos una evaluación experimental extensa tanto en grafos de referencia sintéticos como en redes del mundo real. Mostramos que los resultados tanto en redes sintéticas como en redes del mundo real pueden mejorarse significativamente comenzando desde el cliqué más grande en el vecindario del nodo semilla. Además, nuestros experimentos indican que los algoritmos que utilizan puntuaciones basadas en triángulos superan a otros algoritmos en la mayoría de los casos. Proporcionamos descripciones teóricas, así como implementaciones de código abierto de todos los algoritmos utilizados.