logo móvil

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

Disponible con Suscripción Virtualpro

Artículos


Categoría

Ingeniería y Tecnología

Licencia

Atribución – Compartir igual

Consultas: 4

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.

Documentos Relacionados

Temas Virtualpro