logo móvil
Contáctanos

CoDiS: Detección de Comunidades a través de la Expansión Distribuida de Conjuntos de Semillas en Flujos de Grafos

Autores: Anderson, Austin; Potikas, Petros; Potika, Katerina

Idioma: Inglés

Editor: MDPI

Año: 2023

Descargar PDF

Acceso abierto

Artículo científico
2023

CoDiS: Detección de Comunidades a través de la Expansión Distribuida de Conjuntos de Semillas en Flujos de Grafos


Categoría

Gestión y administración

Subcategoría

Gestión de la tecnología y la inovación

Palabras clave

Detección de comunidades
Comunidades superpuestas
Paralelismo
Modelos de flujo de grafos
Conjuntos de semillas
Tiempo de procesamiento

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 1

Citaciones: Sin citaciones


Descripción
La detección de comunidades ha sido (y sigue siendo) un tema muy importante en varios campos. Desde el marketing y las redes sociales hasta estudios biológicos, la detección de comunidades juega un papel clave en el avance de la investigación en muchos campos diferentes. La investigación sobre este tema originalmente se centró en clasificar nodos en comunidades discretas (comunidades no superpuestas), pero eventualmente avanzó hacia la colocación de nodos en múltiples comunidades (comunidades superpuestas). Desafortunadamente, la detección de comunidades siempre ha sido un proceso ineficiente en términos de tiempo, y los conjuntos de datos son demasiado grandes para procesarlos de manera realista utilizando métodos tradicionales. Debido a esto, los métodos recientes han recurrido al paralelismo y a modelos de flujo de grafos, donde la lista de aristas se accede una arista a la vez. Sin embargo, todos estos métodos, aunque ofrecen una disminución significativa en el tiempo de procesamiento, aún tienen varias limitaciones. Proponemos un nuevo algoritmo paralelo llamado detección de comunidades con conjuntos de semillas (CoDiS), que resuelve el problema de detección de comunidades superpuestas en flujos de grafos. Inicialmente, algunos nodos (conjuntos de semillas) tienen estructuras comunitarias conocidas, y el objetivo es expandir estas comunidades procesando una arista a la vez. La innovación de nuestro enfoque es que divide las comunidades entre los trabajadores de computación paralela, de modo que cada trabajador solo actualiza un subconjunto de todas las comunidades. Al hacerlo, disminuimos el rendimiento del procesamiento de aristas y reducimos la cantidad de tiempo que cada trabajador pasa en cada arista. Crucialmente, eliminamos la necesidad de que cada trabajador tenga acceso a cada comunidad. Los resultados experimentales muestran que somos capaces de lograr una mejora significativa en el tiempo de ejecución sin pérdida de precisión.

Otros recursos que podrían interesarte

Temas Virtualpro