Métricas para comparar grafos

Métricas para la comparación de grafos: una guía para profesionales

Peter Wills, Francois G. Meyer
Arxiv




La comparación de la estructura del grafo es una tarea ubicua en el análisis de datos y el aprendizaje automático, con diversas aplicaciones en campos como neurociencia, seguridad cibernética, análisis de redes sociales y bioinformática, entre otros. El descubrimiento y la comparación de estructuras como las comunidades modulares, los clubes ricos, los centros y los árboles en los datos de estos campos permite comprender los mecanismos generativos y las propiedades funcionales del grafo.



A menudo, dos grafos se comparan mediante una medida de distancia por pares, con una pequeña distancia que indica similitud estructural y viceversa. Las opciones comunes incluyen distancias espectrales (también conocidas como distancias λ) y distancias basadas en afinidades de nodo. Sin embargo, aún no se ha realizado ningún estudio comparativo de la eficacia de estas medidas de distancia para discernir entre topologías de grafos comunes y diferentes escalas estructurales.
En este trabajo, comparamos las métricas de los grafos y las medidas de distancia de uso común, y demostramos su capacidad para discernir entre las características topológicas comunes que se encuentran tanto en los modelos de grafos aleatorios como en los conjuntos de datos empíricos. Presentamos una imagen a escala múltiple de la estructura del grafo, en la que se considera el efecto de la estructura global y local sobre las medidas de distancia. Hacemos recomendaciones sobre la aplicabilidad de diferentes medidas de distancia al problema de datos de grafos empíricos basados ​​en esta vista de escala múltiple. Finalmente, presentamos la biblioteca NetComp de Python que implementa las distancias de los grafos utilizados en este trabajo.

1904 07414