ConvGraph: detección de comunidades de relaciones homogéneas en grafos ponderados
Autores: Muñoz, Héctor; Vicente, Eloy; González, Ignacio; Mateos, Alfonso; Jiménez-Martín, Antonio
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
ConvGraph: detección de comunidades de relaciones homogéneas en grafos ponderados
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Algoritmo propuesto: ConvGraph
Comunidades
Grafos ponderados
Convolución
Densidad de vértices
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 22
Citaciones: Sin citaciones
Este documento propone un nuevo método, ConvGraph, para detectar comunidades en grafos ponderados altamente cohesivos y aislados, donde la suma de los pesos es significativamente mayor dentro que fuera de las comunidades. El método comienza transformando el grafo original en un grafo de línea para aplicar una convolución, una técnica común en el campo de la visión por computadora. Aunque esta técnica fue concebida originalmente para detectar el borde óptimo en imágenes, aquí se utiliza para detectar los bordes óptimos en comunidades identificadas por sus pesos en lugar de por su topología. El método incluye un paso de refinamiento final aplicado a comunidades con una alta densidad de vértices que no pudieron ser detectadas en la primera fase. El algoritmo propuesto fue probado en una serie de grafos sintéticos altamente cohesivos y aislados y en un grafo de exportación del mundo real, teniendo un buen rendimiento en ambos casos.
Descripción
Este documento propone un nuevo método, ConvGraph, para detectar comunidades en grafos ponderados altamente cohesivos y aislados, donde la suma de los pesos es significativamente mayor dentro que fuera de las comunidades. El método comienza transformando el grafo original en un grafo de línea para aplicar una convolución, una técnica común en el campo de la visión por computadora. Aunque esta técnica fue concebida originalmente para detectar el borde óptimo en imágenes, aquí se utiliza para detectar los bordes óptimos en comunidades identificadas por sus pesos en lugar de por su topología. El método incluye un paso de refinamiento final aplicado a comunidades con una alta densidad de vértices que no pudieron ser detectadas en la primera fase. El algoritmo propuesto fue probado en una serie de grafos sintéticos altamente cohesivos y aislados y en un grafo de exportación del mundo real, teniendo un buen rendimiento en ambos casos.