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.¿Qué problemas de escalabilidad están asociados con NetworkX?
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 reciente presentación (las diapositivas están disponibles en github here), se afirmó que:
A diferencia de muchas otras herramientas, NX está diseñado para manejar los datos en una escala relevante para los problemas modernos .. . La mayoría de los algoritmos principales 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 de NetworkX Jefe de Programación me planteó esta pregunta en la lista de correo NetworkX y Aric Hagberg respondió:
Las estructuras de datos utilizadas en NetworkX son apropiadas para el escalado a problemas grandes (por ejemplo, el 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 momento, 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 de cálculo. Los gráficos grandes darán mucha memoria a y eventualmente se agotarán.
NetworkX utiliza NumPy y SciPy para los algoritmos que son principalmente basados en álgebra lineal. En ese caso, el gráfico se representa (copiado) 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.
Parece que tengo problemas para inspeccionar la fuente por el momento. Pero en cualquier caso, considere: el 80% del tiempo se puede gastar en el 20% del código. Mercurial está escrito * en su mayoría * en Python, sin embargo, no he escuchado a una sola persona quejarse de su velocidad en comparación con Git, que es principalmente C. – delnan
Sí, pero también me preocupa la memoria. La representación gráfica en networkx es una biblioteca de Python. ¿Eso quiere decir que solo puedo incluir gráficos más pequeños en la memoria? – conradlee