python - networkx get node attributes
¿Qué problemas de escalabilidad están asociados con NetworkX? (3)
Estoy interesado en el análisis de redes en redes grandes con millones de nodos y decenas de millones de bordes. Quiero ser capaz de hacer cosas como analizar redes de diferentes formatos, encontrar componentes conectados, detectar comunidades y ejecutar medidas de centralidad como PageRank.
Me atrae NetworkX porque tiene una buena API, buena documentación y ha estado en desarrollo activo durante años. Además, porque está en python, debería ser rápido para desarrollar con.
En una presentación reciente (las diapositivas están disponibles en github here ), se afirmó que:
A diferencia de muchas otras herramientas, NX está diseñado para manejar datos en una escala relevante para problemas modernos ... La mayoría de los algoritmos centrales en NX dependen de un código heredado extremadamente rápido.
La presentación también establece que los algoritmos base de NetworkX se implementan en C / Fortran.
Sin embargo, al mirar el código fuente, parece que NetworkX está escrito principalmente en python. No estoy muy familiarizado con el código fuente, pero conozco un par de ejemplos en los que NetworkX usa numpy para realizar levantamientos pesados (que a su vez usa C / Fortran para hacer álgebra lineal). Por ejemplo, el archivo networkx/networkx/algorithms/centrality/eigenvector.py usa numpy para calcular vectores propios.
¿Alguien sabe si esta estrategia de llamar a una biblioteca optimizada como numpy es realmente frecuente en todo NetworkX, o si solo unos pocos algoritmos lo hacen? ¿Alguien puede describir otros problemas de escalabilidad asociados con NetworkX?
Respuesta del programador principal de NetworkX Formulé esta pregunta en la lista de correo de NetworkX, y Aric Hagberg respondió:
Las estructuras de datos utilizadas en NetworkX son apropiadas para escalar a problemas grandes (por ejemplo, la estructura de datos es una lista de adyacencia). Los algoritmos tienen varias propiedades de escala, pero algunos de los que menciona son utilizables (por ejemplo, PageRank, componentes conectados, son complejidad lineal en el número de bordes).
En este punto, NetworkX es un código de Python puro. La estructura de adyacencia está codificada con diccionarios de Python que proporciona una gran flexibilidad a expensas de la memoria y la velocidad computacional. Los gráficos grandes requerirán mucha memoria y eventualmente se agotarán.
NetworkX utiliza NumPy y SciPy para algoritmos que se basan principalmente en álgebra lineal. En ese caso, el gráfico se representa (copia) como una matriz de adyacencia usando matrices NumPy o matrices dispersas SciPy. Esos algoritmos pueden beneficiarse del código heredado C y FORTRAN que se usa bajo el capó en NumPy y SciPY.
El hecho de que la red X esté escrita principalmente en Python no significa que no sea escalable ni que reclame la perfección. Siempre hay una compensación. Si arroja más dinero en sus "máquinas", tendrá tanta escalabilidad como desee además de los beneficios de utilizar una biblioteca de gráficos pythonic.
Si no, hay otras soluciones, ( here y here ), que pueden consumir menos memoria (punto de referencia y ver, creo que igraph está completamente respaldado por C, por lo que lo hará), pero es posible que te pierdas la sensación pitónica de NX.
Esta es una vieja pregunta, pero creo que vale la pena mencionar que graph-tool tiene una funcionalidad muy similar a NetworkX, pero se implementa en C ++ con plantillas (usando Boost Graph Library), y por lo tanto es mucho más rápido ( hasta dos órdenes de magnitud ) y usa mucha menos memoria.
Descargo de responsabilidad: soy el autor de graph-tool.
Tu gran problema será la memoria. Python simplemente no puede manejar decenas de millones de objetos, sin saltar a través de aros en su implementación de clase. La sobrecarga de memoria de muchos objetos es demasiado alta, llega a 2 GB y el código de 32 bits no funciona. Hay formas de evitarlo: usar máquinas tragamonedas, arreglos o numpy. Debería estar bien, porque networkx se escribió para el rendimiento, pero si hay algunas cosas que simplemente no funcionan, verificaría el uso de la memoria.
En cuanto a la escala, los algoritmos son básicamente lo único que importa con los gráficos. Los algoritmos de gráficos tienden a tener escalas realmente feas si se hacen mal, y es muy probable que se realicen en Python como en cualquier otro idioma.