InfoFlow: un algoritmo distribuido para detectar comunidades según la ecuación del mapa
Autores: Fung, Park K.
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
InfoFlow: un algoritmo distribuido para detectar comunidades según la ecuación del mapa
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Sistemas
Palabras clave
Redes
Grandes datos
Computación distribuida
Detección de comunidades
Algoritmo
Ecuación de mapa
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 50
Citaciones: Sin citaciones
Las redes de tamaño formidable se están volviendo cada vez más comunes, incluyendo en ciencias sociales, biología, neurociencia y tecnología. Muchos tamaños de red se espera que desafíen la capacidad de almacenamiento de una sola computadora física. Aquí, tomamos dos enfoques para manejar redes grandes: primero, observamos cómo la tecnología de grandes datos y la computación distribuida son un enfoque emocionante para el almacenamiento y procesamiento de grandes datos. En segundo lugar, la mayoría de las redes pueden ser particionadas o etiquetadas en comunidades, clústeres o módulos, capturando así la esencia de la red mientras se reduce la información detallada, a través de la clase de algoritmos conocida como detección de comunidades. En este documento, combinamos estos dos enfoques, desarrollando un algoritmo de detección de comunidades distribuido para manejar redes grandes. En particular, la ecuación del mapa proporciona una forma de identificar comunidades de red según el flujo de información entre nodos, donde InfoMap es un algoritmo codicioso que utiliza la ecuación del mapa. Desarrollamos matemáticas discretas para adaptar InfoMap a un marco de computación distribuida y luego desarrollamos aún más las matemáticas para un algoritmo codicioso, InfoFlow, que tiene complejidad temporal logarítmica, en comparación con la complejidad lineal en InfoMap. Los resultados de referencia de gráficos de hasta millones de nodos y cientos de millones de aristas confirman la mejora en la complejidad temporal, manteniendo la precisión de las comunidades. Así, desarrollamos un algoritmo de detección de comunidades basado en la ecuación del mapa adecuado para el procesamiento de datos de redes grandes.
Descripción
Las redes de tamaño formidable se están volviendo cada vez más comunes, incluyendo en ciencias sociales, biología, neurociencia y tecnología. Muchos tamaños de red se espera que desafíen la capacidad de almacenamiento de una sola computadora física. Aquí, tomamos dos enfoques para manejar redes grandes: primero, observamos cómo la tecnología de grandes datos y la computación distribuida son un enfoque emocionante para el almacenamiento y procesamiento de grandes datos. En segundo lugar, la mayoría de las redes pueden ser particionadas o etiquetadas en comunidades, clústeres o módulos, capturando así la esencia de la red mientras se reduce la información detallada, a través de la clase de algoritmos conocida como detección de comunidades. En este documento, combinamos estos dos enfoques, desarrollando un algoritmo de detección de comunidades distribuido para manejar redes grandes. En particular, la ecuación del mapa proporciona una forma de identificar comunidades de red según el flujo de información entre nodos, donde InfoMap es un algoritmo codicioso que utiliza la ecuación del mapa. Desarrollamos matemáticas discretas para adaptar InfoMap a un marco de computación distribuida y luego desarrollamos aún más las matemáticas para un algoritmo codicioso, InfoFlow, que tiene complejidad temporal logarítmica, en comparación con la complejidad lineal en InfoMap. Los resultados de referencia de gráficos de hasta millones de nodos y cientos de millones de aristas confirman la mejora en la complejidad temporal, manteniendo la precisión de las comunidades. Así, desarrollamos un algoritmo de detección de comunidades basado en la ecuación del mapa adecuado para el procesamiento de datos de redes grandes.