logo móvil
Contáctanos

Detección de comunidades locales en grafos dinámicos utilizando centralidad personalizada

Autores: Nathan, Eisha; Zakrzewska, Anita; Riedy, Jason; Bader, David A.

Idioma: Inglés

Editor: MDPI

Año: 2017

Descargar PDF

Acceso abierto

Artículo científico
2017

Detección de comunidades locales en grafos dinámicos utilizando centralidad personalizada


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Gráficos
Datos
Detección de comunidades
Medidas de centralidad
Gráficos dinámicos
Clasificación personalizada

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 26

Citaciones: Sin citaciones


Descripción
Analizar grafos masivos plantea desafíos debido a la gran cantidad de datos disponibles. Extraer subgrafos relevantes más pequeños permite una visualización y análisis adicionales que de otro modo serían demasiado intensivos computacionalmente. Además, muchos conjuntos de datos reales están en constante cambio y requieren algoritmos para actualizarse a medida que evoluciona el grafo. Este trabajo aborda el tema de la detección de comunidades locales, o expansión de conjuntos de semillas, utilizando medidas de centralidad personalizadas, específicamente PageRank y centralidad de Katz. Presentamos un método para actualizar eficientemente comunidades locales en grafos dinámicos. Al actualizar los vectores de clasificación personalizados, podemos actualizar incrementalmente la comunidad local correspondiente. Aplicando nuestros métodos a grafos del mundo real, logramos obtener aceleraciones de hasta 60 veces en comparación con la recomputación estática, manteniendo un recuerdo promedio de 0.94 de los vértices altamente clasificados devueltos. A continuación, investigamos cómo las aproximaciones de un vector de centralidad afectan la comunidad local resultante. Específicamente, nuestro método garantiza que los vértices devueltos en la comunidad sean los vértices altamente clasificados de una métrica de centralidad personalizada.

Otros recursos que podrían interesarte

Temas Virtualpro