Quels sont les problèmes d'évolutivité associés à NetworkX?
je suis intéressé par l'analyse du réseau sur les grands réseaux, avec des millions de nœuds et des dizaines de millions de bords. Je veux être capable de faire des choses comme analyser des réseaux à partir de nombreux formats, trouver des composants connectés, détecter des communautés, et exécuter des mesures de centralité comme PageRank.
Je suis attiré par NetworkX parce qu'il a une bonne api, une bonne documentation, et est en développement actif depuis des années. De plus, parce qu'il est en python, il devrait être rapide à développer avec.
Dans une récente présentation (diapositives sont disponibles sur github ici), il a été affirmé que:
contrairement à beaucoup d'autres outils, NX est conçu pour traiter des données sur une échelle pertinentes aux problèmes modernes...La plupart des algorithmes de base de NX s'appuient sur du code d'héritage extrêmement rapide.
la présentation indique également que les algorithmes de base de NetworkX sont implémentés dans C/Fortran.
Cependant, en regardant la source code, on dirait que NetworkX est surtout écrit en python. Je ne suis pas très familier avec le code source, mais je suis au courant de quelques exemples où NetworkX utilise numpy pour faire du levage lourd (qui à son tour utilise C/Fortran pour faire de l'algèbre linéaire). Par exemple, le fichier networkx/networkx/algorithms/centrality/eigenvector.py utilise numpy pour calculer les vecteurs propres.
Est-ce que quelqu'un sait si cette stratégie d'appeler une bibliothèque optimisée comme numpy est vraiment répandue dans NetworkX, ou si seulement quelques algorithmes le font? Aussi n'importe qui peut décrire d'autres problèmes d'évolutivité associés à NetworkX?
Réponse de NetworkX Programmeur en chef J'ai posé cette question sur la liste de diffusion de NetworkX, et Aric Hagberg a répondu:
Les structures de données utilisées dans NetworkX sont appropriées pour mettre à l'échelle problèmes importants (par exemple, la structure des données est une liste de contiguïté). Le les algorithmes ont diverses propriétés d'échelle, mais certains de ceux que vous les mentions sont utilisables (p. ex. PageRank, connected composants, sont linéaires la complexité dans le nombre d'arêtes).
A ce point, NetworkX est du pur code Python. La structure de contiguïté est encodé avec des dictionnaires Python qui offre une grande flexibilité au détriment de la mémoire et de vitesse de calcul. Grands graphiques prendre beaucoup de mémoire et vous finirez par en manquer.
NetworkX utilise NumPy et SciPy pour les algorithmes qui sont principalement basé sur l'algèbre linéaire. Dans ce cas, le graphe est représenter (copié) comme matrice de contiguïté à L'aide de matrices NumPy ou de SciPy des matrices éparses. Ces algorithmes peuvent bénéficier de l'héritage C et Code FORTRAN utilisé sous la hotte en NumPy et SciPY.
3 réponses
votre grand problème sera la mémoire. Python simplement ne peut pas manipulez des dizaines de millions d'objets, sans sauter à travers des cerceaux dans votre implémentation de classe. La mémoire aérienne de beaucoup d'objets est trop élevée, vous frappez 2Go, et le code 32 bits ne fonctionnera pas. Il y a des moyens de contourner ça - en utilisant des machines à sous, des tableaux, ou des puces. devrait soyez OK, parce que networkx a été écrit pour la performance, mais s'il y a quelques choses qui ne fonctionnent pas je vérifierais votre utilisation de la mémoire.
Comme pour la mise à l'échelle, les algorithmes sont essentiellement la seule chose qui importe avec les graphiques. Les algorithmes de graphe ont tendance à avoir vraiment mise à l'échelle laide si elles sont faites mal, et elles sont tout aussi susceptibles d'être faites bien en Python que n'importe quel autre langage.
C'est une vieille question, mais je pense qu'il vaut la peine de mentionner que graphique de l'outil a une fonctionnalité très similaire à NetworkX, mais il est implémenté en C++ avec des modèles (en utilisant la bibliothèque Boost Graph), et est donc beaucoup plus rapide (jusqu'à deux ordres de grandeur) et utilise beaucoup moins de mémoire.
avertissement: je suis l'auteur de graph-tool.
le fait que networkX soit principalement écrit en python ne signifie pas qu'il n'est pas évolutif, ni qu'il revendique la perfection. Il y a toujours un compromis. Si vous dépensez plus d'argent sur vos "machines", vous aurez autant d'évolutivité que vous le souhaitez, plus les avantages d'utiliser une bibliothèque graphique pythonic.
Si non, il y a d'autres solutions, ( ici et ici), qui peut consommer moins de mémoire ( benchmark et voir, je pense que igraph est entièrement c backed donc il va), mais vous pouvez manquer la sensation pythonique de NX.