Un algoritmo codicioso para la detección de comunidades basado en la superposición de vecindarios
Autores: Meghanathan, Natarajan
Idioma: Inglés
Editor: MDPI
Año: 2016
Acceso abierto
Artículo científico
2016
Un algoritmo codicioso para la detección de comunidades basado en la superposición de vecindarios
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Superposición de vecindarios
Borde
Nodos
Proporción
Puntuación de modularidad
Detección de comunidades
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 42
Citaciones: Sin citaciones
El solapamiento de vecindario (NOVER) de un borde se define como la proporción entre el número de nodos que son vecinos de ambos y el número de nodos que son vecinos de al menos uno. En este documento, hipotetizamos que un borde con una puntuación NOVER más baja conecta dos o más conjuntos de vértices, con muy pocos bordes (además del borde) conectando vértices de un conjunto a otro. En consecuencia, proponemos un algoritmo voraz para eliminar iterativamente los bordes de una red en orden creciente de su solapamiento de vecindario y calcular la puntuación de modularidad del componente(s) de red resultante después de la eliminación de cada borde. Los componentes de red que tienen la mayor puntuación acumulativa de modularidad se identifican como las diferentes comunidades de la red. Evaluamos el rendimiento del algoritmo de detección de comunidades basado en NOVER propuesto en nueve gráficos de red del mundo real y comparamos el rendimiento con el algoritmo de Louvain basado en la agregación multinivel, así como con las versiones originales y eficientes en tiempo del algoritmo de detección de comunidades de Girvan-Newman (GN) basado en la intermediación de borde.
Descripción
El solapamiento de vecindario (NOVER) de un borde se define como la proporción entre el número de nodos que son vecinos de ambos y el número de nodos que son vecinos de al menos uno. En este documento, hipotetizamos que un borde con una puntuación NOVER más baja conecta dos o más conjuntos de vértices, con muy pocos bordes (además del borde) conectando vértices de un conjunto a otro. En consecuencia, proponemos un algoritmo voraz para eliminar iterativamente los bordes de una red en orden creciente de su solapamiento de vecindario y calcular la puntuación de modularidad del componente(s) de red resultante después de la eliminación de cada borde. Los componentes de red que tienen la mayor puntuación acumulativa de modularidad se identifican como las diferentes comunidades de la red. Evaluamos el rendimiento del algoritmo de detección de comunidades basado en NOVER propuesto en nueve gráficos de red del mundo real y comparamos el rendimiento con el algoritmo de Louvain basado en la agregación multinivel, así como con las versiones originales y eficientes en tiempo del algoritmo de detección de comunidades de Girvan-Newman (GN) basado en la intermediación de borde.