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
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.
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.