Benchmark de los populares paquetes de grafos / redes v2
Quasilinear Musings
Esta es una actualización de un punto de referencia de publicaciones populares de gráficos / paquetes de red. Este estudio tiene como objetivo servir como punto de partida para cualquier persona interesada en gráficos aplicados o análisis de redes. Los paquetes de red destacados ofrecen una API conveniente y estandarizada para modelar datos como gráficos y extraer información relacionada con la red. Algunos casos de uso comunes incluyen encontrar el camino más corto entre entidades o calcular una medida de centralidad como el puntaje de rango de página.
Para replicar el ejercicio de referencia y los códigos completos, consulte mi repositorio de github. Las instrucciones sobre cómo configurar e instalar los paquetes también se encuentran en el repositorio. Si usted es un mantenedor de paquetes y desea incluir su paquete, no dude en hacer una solicitud de extracción. Alternativamente, si está interesado en un algoritmo particular que no cubro, siéntase libre de enviar también un RP y lo incluiré en el punto de referencia como parte de la próxima ejecución.
Actualizaciones principales
Aquí hay una lista de los principales desarrollos desde mi publicación anterior en abril de 2019:
- Los paquetes de Python ahora son referenciales usando timeit en lugar de cprofile para un tiempo de ejecución más preciso y para permitir una mejor comparación entre paquetes1
- Los resultados se comparan utilizando la mediana del tiempo de ejecución en lugar de la media.
- Para todos los paquetes, el conjunto de datos se lee como un gráfico dirigido y el tiempo de referencia cubre tanto el tiempo de ejecución analítico como la asignación de memoria.
- Lightgraphs v2.0-dev se incluye en el ejercicio de referencia.4 Es la primera biblioteca de Julia que se agrega al estudio. Siga leyendo para averiguar cómo le va con el resto.
- igraph, el titular en el espacio con enlaces populares de R, Mathematica y Python ha sido actualizado a v0.8. ¡El último lanzamiento importante fue en 2014! Para obtener una lista completa de nuevas características y mejoras, consulte la página de lanzamiento de github de igraph
- SNAP, otro incondicional en el espacio lanza v5.0, que finalmente admite Python 3 y pip install.
- Networkit lanza v6.0.
- Los procedimientos de instalación rápidos en SNAP, graph-tool y networkx, ya que ahora admiten conda o pip. ¡Mira mis instrucciones de configuración para ver lo sencillo que es instalar uno de estos paquetes ahora!
Los cambios en la metodología de referencia, así como la estandarización de cómo se leen los datos y se muestran los resultados, permite establecer mejores comparaciones entre los paquetes.
Al mismo tiempo, las nuevas características y mejoras en los paquetes han hecho que el análisis de red de alto rendimiento sea extremadamente accesible para cualquier analista, felicitaciones a todos los desarrolladores que lo han hecho posible.
Metodología
El punto de referencia se llevó a cabo utilizando una instancia de Google Compute n1-standard-16 (16vCPU Haswell 2.3GHz, 60 GB de memoria). Consulte la carpeta de configuración para obtener instrucciones de instalación más detalladas.
En su caso, todos los algoritmos se probaron utilizando los 16 núcleos. Comparé 6 paquetes diferentes:
- graph-tool, v2.31 (Peixoto 2014)
- igraph, v0.8.2 (Csardi y Nepusz 2006)
- networkit, v6.1.0 (Staudt, Sazonovs y Meyerhenke 2016)
- networkx, v2.4 (Hagberg, Swart y S Chult 2008)
- SNAP, v5.0.0 (Leskovec y Sosič 2016)
- lightgraphs, v2.0-dev (Seth Bromberger y colaboradores 2017)
Networkx está escrito en Python, mientras que los otros cuatro paquetes, con la excepción de lightgraphs, se basan en C / C ++ pero tienen API de Python. Igraph también tiene un enlace R y Mathematica, aunque el punto de referencia se llevó a cabo en Python. Lightgraphs ofrece una plataforma de alto rendimiento para el análisis de redes y gráficos en Julia.
Seleccionar qué tareas comparar no es realmente una decisión trivial con cada paquete que ofrece varias herramientas y capacidades. Al final, decidí centrarme en 5 problemas específicos:
- cargando los datos
- ruta más corta de una sola fuente
- rango de página
- descomposición del núcleo k
- componentes fuertemente conectados
La carga es más una tarea de E / S, mientras que los otros 4 son algoritmos de gráficos comunes.
Descargo de responsabilidad:
- En la medida de lo posible, trato de especificar los mismos parámetros para cada algoritmo, pero las diferencias en la API entre los paquetes podrían traducirse en diferencias reales en la forma en que se ejecuta el algoritmo y el resultado final. Por ejemplo, algunas de las diferencias observadas en el rendimiento podrían ser el resultado de diferentes criterios de detención utilizados o diferentes implementaciones de algoritmos, etc.
- Para los lighgraphs, los datos se representan utilizando la estructura SimpleGraphs. Se podría lograr un mejor rendimiento utilizando la estructura StaticGraphs a expensas de la mutabilidad.
- El benchmark de rendimiento captura las diferencias de tiempo de ejecución entre paquetes en algoritmos de gráficos básicos en gráficos dirigidos. Otras métricas importantes como el consumo de memoria están fuera del alcance de este estudio. Las diferencias en la implementación entre gráficos dirigidos y no dirigidos o algoritmos ponderados y no ponderados limitan la generalización entre las otras funciones.
Conjunto de datos
En el ejercicio se utilizaron 3 conjuntos de datos de la Colección de conjuntos de datos de red grande de Stanford (Leskovec y Krevl 2014):
Si bien es más fácil clasificar los paquetes según el tiempo de ejecución de los algoritmos, es solo una de las muchas consideraciones de lo que hace que un paquete sea bueno. Intento ofrecer una vista más subjetiva basada en mi experiencia con estos paquetes.
Benchmarks relacionados
Aquí hay una lista de otros puntos de referencia comparativos para que el espectador interesado los vea:
- Comparación de rendimiento de Graph-tool (Peixoto 2015), compara graph-tool con igraph y networkx en la ruta más corta de una sola fuente, rango de página, k-core, árbol de expansión mínima y algoritmos de betweeness.
- Leskovec y Sosic (2016), comparan snap con igraph y networkx en la generación y carga de gráficos Erdos-Renyi, rango de página, coeficiente de agrupamiento, componentes débilmente conectados, extracción de 3 núcleos de una red y prueba de existencia de borde.
- Staudt, Sazonovs y Meyerhenke (2016), comparan networkit con igraph y graph-tool en la búsqueda de amplitud, componentes conectados, descomposición del núcleo, cálculo del diámetro de un gráfico, detección de comunidad, coeficiente de agrupación, rango de página, algoritmos de betweeness .
- Graph500 (Murphy et al. 2010), un punto de referencia notable basado en gráficos basado en la búsqueda de amplitud, principalmente para comparar supercomputadores en lugar de paquetes.
La mayoría de los estudios de comparación de paquetes se escribieron en 2015/2016. Desde entonces, ha habido mejoras sustanciales en el campo y será interesante ver los cambios a lo largo del tiempo.
Resultados
Todos los tiempos reportados son la mediana de la capturada para una tarea en particular. Para el conjunto de datos de Amazon y Google, todos los algoritmos se ejecutaron 100 veces, mientras que para el conjunto de datos Pokec se realizaron 10 ejecuciones para cada paquete. Networkx es la excepción. Dado que es más lento en una magnitud significativa (aproximadamente 10 veces más que la biblioteca más lenta), solo se realizaron 10 ejecuciones en el conjunto de datos de Amazon y Google y 1 en el conjunto de datos Pokec. Por ejemplo, tardó 68 segundos en ejecutar el problema de ruta más corta de una sola fuente en el conjunto de datos Pokec en networkx en comparación con 0.62 segundos para networkit (el siguiente más lento). Por lo tanto, lo dejé fuera de las tramas de comparación.
Estos son los tiempos de ejecución de los otros paquetes en los 3 conjuntos de datos de referencia:
Los resultados completos se pueden ver en la tabla a continuación:
Otra forma de ver los resultados es calculando la cantidad de veces que uno podría ejecutar un algoritmo particular dado el tiempo que toma networkx. Esta métrica da una indicación de cuántas veces más rendimiento tiene un algoritmo particular en comparación con networkx. La puntuación calculada con el conjunto de datos de Google se muestra a continuación:
Cargando
Los conjuntos de datos SNAP se leyeron como un archivo delimitado por tabuladores en un formato de gráfico dirigido. De las parcelas anteriores, igraph y networkit lideran la tarea de carga de gráficos. La diferencia en la velocidad de lectura se puede atribuir a las diferencias en la carga, así como a los métodos de construcción de gráficos (posiblemente de la diferente representación interna de los gráficos) .5
Por ejemplo, la graph-tool utiliza el código Python para analizar la entrada, mientras que igraph y networkit usan las bibliotecas C para leer los archivos que resultan en un mejor rendimiento.6
Algoritmos
Todas las bibliotecas destacadas son mucho más eficaces que networkx.
La biblioteca de menor rendimiento (SNAP) es 13 veces más rápida en el problema de ruta más corta de una sola fuente, 14 veces más rápido en el rango de página, 32 veces más rápido en el cálculo del núcleo k y 5 veces más rápido en la identificación de componentes conectados.
Lightgraphs es ~ 300 veces más rápido que networkx en el problema de ruta más corta de una sola fuente, y aproximadamente 10 veces más rápido que los otros competidores. Logra la aceleración con una versión multiproceso del algoritmo.
Lightgraphs y networkit se destacan en el algoritmo de rango de página, con graph-tool que exhiben el siguiente mejor rendimiento.7
Una vez más, lightgraphs se desempeña extremadamente bien en la descomposición de k-core, siendo más de> 250 veces más rápido que networkx. Nota: En el primer estudio de referencia, networkit se desempeñó increíblemente bien en esta medida cuando el conjunto de datos se leyó como un gráfico no dirigido. No parece que la funcionalidad de subprocesos múltiples se extienda a gráficos dirigidos.
La graph-tool, lightgraphs y la networkx funcionaron igualmente bien en el fuerte problema de los componentes conectados.
Además de que SNAP está en el lado más lento, el resto de los paquetes se desempeñaron muy bien en todas las tareas.
¿Cómo han mejorado los paquetes con respecto al año anterior? 8 Igraph ciertamente mejoró tanto en el rango de página como en la prueba de componentes conectados con resultados al menos 2 veces más rápidos desde la ejecución anterior. Networkit ha hecho grandes avances en la carga utilizando un nuevo formato de gráfico binario, así como una mejora en la búsqueda de amplitud y los componentes conectados. El cambio de lightgraphs 1.x a 2.0 también ha llevado a ganancias significativas en el rendimiento general con muchos algoritmos de subprocesos múltiples ahora disponibles.
Multithreads
Además de tener algoritmos eficientes de un solo hilo, los paquetes como la graph-tool, networkit y lightgraphs también aprovechan el procesamiento paralelo para acelerar los cálculos.
En esta sección, comparo el rendimiento en 1, 4, 8 y 16 núcleos para estos 3 paquetes.10 El conjunto de datos web de Google se utilizó para esta parte del análisis.
Un problema que enfrenté cuando utilicé la graph-tool y networkx es que no es inmediatamente evidente qué algoritmo tiene implementaciones de subprocesos múltiples. Ejecutar el punto de referencia ayuda a arrojar algo de luz en esta área.
Graph-tool, networkit y lightgraphs ofrecen una implementación roscada de rango de página. Tanto networkit como lightgraphs tienen una versión roscada del algoritmo k-cores, aunque la versión networkit parece aplicarse solo a gráficos no dirigidos. Solo los lightgraphs proporcionan una versión roscada del problema de la ruta más corta de fuente única fuera de la caja.
Primero, veamos cómo difiere el rendimiento a medida que aumentamos el número de hilos en el algoritmo de Pagerank.
Para la graph-tool y networkx, vemos una aceleración sustancial al aumentar de 1 a 4 a 8 núcleos. Sin embargo, los rendimientos decrecientes se activan al aumentar de 8 a 16 núcleos. Por ejemplo, el tiempo de ejecución del algoritmo de rango de página es 0.42s para 8 núcleos y 0.28s usando 16 núcleos para la graph-tool, mientras que para networkit fue 0.098s para 8 núcleos y 0.1s para 16 núcleos. Lightgraphs es una anomalía aquí, ya que su rendimiento es realmente rápido incluso en 1 hilo y relativamente consistente en todas las configuraciones.11
A continuación, echamos un vistazo al algoritmo roscado k-core de lightgraphs.
Al ejecutarse en un hilo, lightgraphs tarda 0.57s para ejecutar el algoritmo k-core, un poco más lento que la graph-tool a 0.39s pero más rápido que networkit a 0.83s. Correr con los 16 núcleos le da una aceleración de 3.5x.
Finalmente, echamos un vistazo al algoritmo de ruta más corta de fuente única roscada entre lightgraphs.
Este gráfico nos da una idea de cómo lightgraphs superan a los otros paquetes en el punto de referencia de ruta más corta de una sola fuente. Si tuviéramos que considerar solo el rendimiento de un solo hilo, lightgraphs (0.08s) serían comparables a la graph-tool. El subprocesamiento múltiple le da una velocidad de aproximadamente 8x.
Los resultados de la ruta más corta de k-core y de fuente única también exhiben rendimientos decrecientes que van de 8 a 16 núcleos. Esto podría deberse al tamaño del conjunto de datos y sería interesante saber si esto también es válido para el conjunto de datos pokec.
Otras Consideraciones
También hay otros puntos importantes a considerar antes de hacer un cambio o comenzar un proyecto en uno de estos paquetes. Además de la evaluación comparativa numérica pura, se deben examinar otras consideraciones, como la curva de aprendizaje, la documentación, la popularidad y el apoyo.
Paquetes
Primero, los algoritmos disponibles difieren bastante significativamente entre los paquetes. Los usuarios interesados en cambiar a uno de estos paquetes deben leer la documentación en la lista de características disponibles. Por ejemplo, si bien todos contienen las herramientas básicas necesarias para manipular redes, la graph-tool carece de las herramientas de agrupación modular más habituales, pero tiene funcionalidades adicionales en la inferencia estadística en gráficos que utilizan modelos de bloques estocásticos. igraph también agrega una función de inclusión espectral en la actualización reciente.
La visualización de redes también es una parte importante de la cadena de herramientas analíticas. Igraph implementa bastantes algoritmos de diseño y los representa usando la biblioteca de El Cairo. Snap es compatible con graphviz, mientras que la graph-tool es compatible con graphviz y cairo. Networkit adopta un enfoque diferente y se basa en networkx para dibujar, al tiempo que proporciona soporte e integración con Gephi a través de su complemento de transmisión. Lightgraphs también se basa en otros paquetes de gráficos en el ecosistema de Julia y tiene una estrecha integración con otros paquetes de JuliaGraph como GraphPlot.jl.
API
Alejarse de Python nativo o R significa que la sintaxis de los paquetes a veces puede ser bastante complicada. Comparemos la sintaxis para derivar una matriz de la distancia de ruta más corta desde un nodo de origen.
networkx:
nx.shortest_path_length(g, nodeid)
igraph:
g.shortest_paths([g.vs[node_index]])[0]
graph-tool:
shortest_distance(g, g.vertex(node_index)).a
networkit:
distance.BFS(g, node_index, storePaths=False).run().getDistances(False)
snap:
NIdToDistH = snap.TIntH()
snap.GetShortPath(g, node_index, NIdToDistH, True)
[(item, NIdToDistH[item]) for item in NIdToDistH]
lightgraphs:
distances(g, node_index, BreadthFirst(sort_alg=RadixSort))
distances(g, node_index, ThreadedBreadthFirst())
Si bien esto puede ser una cuestión de gustos, considero que la API de SNAP es la más engorrosa, ya que uno tiene que definir una variable adicional (con el tipo de variable correcto) para almacenar los resultados antes de ejecutarla. La ejecución de funciones más avanzadas en graph-tool y networkx también requiere que el usuario defina previamente las variables con el tipo correcto para almacenar resultados. Esta es la compensación que se paga por paquetes más efectivos.
Lightgraphs ofrece implementaciones no roscadas y roscadas de algoritmos particulares y depende del usuario especificar el algoritmo a ejecutar.12 Por otro lado, networkit y la graph-tool 'automáticamente' usa la implementación roscada a través de openmp, aunque esto se aplica solo a los seleccionados algoritmos y no está claro de inmediato sin profundizar en el código fuente o probarlo (como este punto de referencia).
Código fuente
Además de networkx, los otros paquetes basados en python tienen código fuente subyacente en C / C ++ y dependen de otras bibliotecas, como la biblioteca de impulso y la metaprogramación de plantillas. Esto hace que sumergirse en el código fuente sea más difícil a menos que esté bien versado en C / C ++. La simplicidad de networkx y el hecho de que está escrito en Python facilita la comprensión de la lógica de los algoritmos de red y una buena herramienta de enseñanza. Las Lightgraphs que se escriben completamente en Julia también son relativamente legibles, pero requieren aprender otro idioma para dominarlo realmente.
Soporte y documentación
El soporte al usuario y la documentación son realmente importantes cuando uno quiere usar el proyecto en una configuración de proyecto real. Networkx es, con mucho, el ganador en esta categoría con más de 4k estrellas github y muchos problemas documentados en github y stackoverflow. También grabo ferias decentemente con más de mil estrellas en sus diferentes módulos, aunque no hay actualizaciones consistentes (hasta hace poco) o hojas de ruta de desarrollo.
La graph-tool y networkx tienen seguidores mucho más pequeños, aunque los creadores parecen relativamente receptivos a los problemas del usuario y los paquetes están en desarrollo activo.
lightgraphs es probablemente el equivalente de networkx en Julia y actualmente se encuentra cerca de 450 estrellas gihub y está en desarrollo muy activo. Las mejoras de v1.xa 2.0 en los últimos meses son realmente increíbles.
Conclusión
Aquí están mis tres conclusiones principales de este estudio. Primero, es mucho más fácil instalar cualquiera de estos paquetes. Ya no es necesario revisar toda la documentación y jugar con la instalación. La mayoría de los paquetes ahora se pueden instalar desde administradores de paquetes populares con una sola línea. Algunos incluso ofrecen versiones de Docker.
En segundo lugar, ha habido una mejora significativa en todos los paquetes. No estoy seguro de si esto se debe a que el análisis de red se ha vuelto más popular o es simplemente una coincidencia que la mayoría de los encargados del paquete decidieron lanzar actualizaciones importantes en 2019. De cualquier manera, son buenas noticias para los usuarios finales que pueden disfrutar de 2- Aceleración 10x en algoritmos populares.
En tercer lugar, para la mayoría de estos paquetes, el tiempo de ejecución de un algoritmo es relativamente comparable, especialmente si se basa en un lenguaje compilado (C, C ++, Julia). Vea los resultados de los componentes conectados para ver un ejemplo. Si la velocidad es de suma importancia, la siguiente consideración es probablemente encontrar el paquete correcto que implemente una versión roscada del algoritmo.
Si está buscando recomendaciones sobre paquetes que provienen de un fondo R / Python (como yo), recomendaría networkx para retomar los conceptos básicos de los algoritmos de gráficos. Si está buscando un siguiente paso y una solución más eficiente, igraph y graph-tool y networkit parecen buenas opciones, siempre que los algoritmos listos para usar le ofrezcan todo lo que necesita. Si está dispuesto a considerar un nuevo lenguaje, lightgraphs es muy prometedor y parece tener una curva de aprendizaje más baja que otras alternativas C / C ++. Por supuesto, si tiene un problema específico que resolver, sin duda vale la pena compararlo, dado que ningún paquete es ampliamente superior a todos los demás. En ese caso, siéntase libre de ampliar mi código y modificarlo para satisfacer sus necesidades.
Referencias
Csardi, Gabor, and Tamas Nepusz. 2006. “The Igraph Software Package for Complex Network Research.” InterJournal Complex Systems: 1695.
https://igraph.org/.
Hagberg, Aric, Pieter Swart, and Daniel S Chult. 2008. “Exploring Network Structure, Dynamics, and Function Using Networkx.” Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
Leskovec, Jure, and Andrej Krevl. 2014. “SNAP Datasets: Stanford Large Network Dataset Collection.”
http://snap.stanford.edu/data.
Leskovec, Jure, and Rok Sosic. 2016. “SNAP: A General Purpose Network Analysis and Graph Mining Library.”
http://arxiv.org/abs/1606.07550.
Leskovec, Jure, and Rok Sosič. 2016. “SNAP: A General-Purpose Network Analysis and Graph-Mining Library.” ACM Transactions on Intelligent Systems and Technology (TIST) 8 (1): 1.
Murphy, Richard C, Kyle B Wheeler, Brian W Barrett, and James A Ang. 2010. “Introducing the Graph 500.” Cray Users Group (CUG) 19: 45–74.
Peixoto, Tiago P. 2014. “The Graph-Tool Python Library.” Figshare.
https://doi.org/10.6084/m9.figshare.1164194.
———. 2015. “Graph-Tool Performance Comparison.”
https://graph-tool.skewed.de/performance.
Seth Bromberger, James Fairbanks, and other contributors. 2017. “JuliaGraphs/Lightgraphs.jl: An Optimized Graphs Package for the Julia Programming Language.”
https://doi.org/10.5281/zenodo.889971.
Staudt, Christian L, Aleksejs Sazonovs, and Henning Meyerhenke. 2016. “NetworKit: A Tool Suite for Large-Scale Complex Network Analysis.”
Network Science 4 (4): 508–30.
- Hay una sobrecarga adicional del código de creación de perfiles en comparación con solo cronometrarlo.
- La mediana es más robusta que los valores atípicos. Resultados completos: min, median, mean, max están disponibles en los archivos de salida respectivos para cada ejecución de creación de perfiles para un conjunto de datos.
- Esto hace que las comparaciones entre paquetes sean más comparables en comparación con la ejecución anterior.
- Los resultados iniciales basados en v1.3 se comprometieron con el repositorio a principios de año. Este punto de referencia revisado utiliza v2.0-dev que se puede extraer de la rama maestra.
- Probablemente se requiera un ejercicio de referencia basado en la construcción pura para separar los dos factores.
- Graph-tool debería leer de otros tipos de archivos, como graphml o dot, mucho más rápido, aunque en realidad no lo probé.
- Nota: esto podría deberse a diferencias en los criterios de detención. Matthew Galati de SAS señaló que para el algoritmo de rango de página, networkit (a partir de la versión 6.0) usa la norma L2 como criterio de detención, mientras que otros paquetes usan la norma L1. Esto significa que está haciendo menos iteraciones y la velocidad es algo artificial↩
- Este párrafo se basa en mi experiencia de volver a ejecutar el punto de referencia anterior antes de realizar cambios en los códigos. Debido a las diferencias en la metodología, es decir, timeit vs cprofile, así como la mediana vs la media, uno debería esperar que todos los resultados sean más bajos que las ejecuciones anteriores, que son. Destaco resultados que difieren significativamente de la ejecución anterior.
- Graph-tool y networkit dependen de openmp y se puede establecer el número de subprocesos utilizando la función openmp_set_num_threads o las funciones setNumberOfThreads respectivamente. Para lightgraphs, la variable de entorno JULIA_NUM_THREADS debe configurarse antes de ejecutar las funciones de subprocesos múltiples.
- lightgraphs ofrecen una versión explícita del algoritmo con o sin hilos. Los resultados de subprocesos individuales para lightgraphs se informan utilizando el algoritmo sin subprocesos ejecutado en un solo núcleo.
- La versión "sin subprocesos" utiliza BLAS, que es inherentemente multiproceso.
- Esto se basa en la versión de desarrollo de Lightgraphs v2.0-dev. Los usuarios de versiones 1.x existentes pueden encontrarlo ligeramente diferente.
