TL/DR :La centralité intermédiaire est un calcul très lent, vous souhaiterez donc probablement utiliser une mesure approximative en considérant un sous-ensemble de myk nœuds où myk est un nombre bien inférieur au nombre de nœuds dans le réseau, mais suffisamment grand pour être statistiquement significatif (NetworkX a une option pour cela :betweenness_centrality(G, k=myk) .
Je ne suis pas du tout surpris que cela prenne beaucoup de temps. La centralité intermédiaire est un calcul lent. L'algorithme utilisé par networkx est O(VE) où V est le nombre de sommets et E le nombre d'arêtes. Dans votre cas VE = 10^13 . Je m'attends à ce que l'importation du graphique prenne O(V+E) temps, donc si cela prend suffisamment de temps pour que vous puissiez dire que ce n'est pas instantané, alors O(VE) ça va être douloureux.
Si un réseau réduit avec 1 % des nœuds et 1 % des arêtes (donc 20 000 nœuds et 50 000 arêtes) prendrait un temps X, alors le calcul souhaité prendrait 10 000 X. Si X est une seconde, alors le nouveau calcul est proche de 3 heures, ce qui me semble incroyablement optimiste (voir mon test ci-dessous). Donc, avant de décider qu'il y a quelque chose qui ne va pas avec votre code, exécutez-le sur des réseaux plus petits et obtenez une estimation de ce que devrait être le temps d'exécution pour votre réseau.
Une bonne alternative consiste à utiliser une mesure approximative. La mesure d'intermédiarité standard considère chaque paire de nœuds et les chemins entre eux. Networkx propose une alternative qui utilise un échantillon aléatoire de seulement k nœuds, puis trouve les chemins les plus courts entre ces k nœuds et tous les autres nœuds du réseau. Je pense que cela devrait accélérer l'exécution en O(kE) temps
Donc, ce que vous utiliseriez est
betweenness_centrality(G, k=k)
Si vous voulez avoir des limites sur la précision de votre résultat, vous pouvez faire plusieurs appels avec une petite valeur de k , assurez-vous qu'ils sont relativement proches, puis prenez le résultat moyen.
Voici quelques-uns de mes tests rapides de temps d'exécution, avec des graphiques aléatoires de (V,E)=(20,50); (200 500); et (2000,5000)
import time
for n in [20,200,2000]:
G=nx.fast_gnp_random_graph(n, 5./n)
current_time = time.time()
a=nx.betweenness_centrality(G)
print time.time()-current_time
>0.00247192382812
>0.133368968964
>15.5196769238
Ainsi, sur mon ordinateur, il faut 15 secondes pour gérer un réseau qui fait 0,1 % de la taille du vôtre. Il faudrait environ 15 millions de secondes pour créer un réseau de la même taille que le vôtre. C'est 1,5*10^7 secondes, soit un peu moins de la moitié de pi*10^7 secondes. Étant donné que pi*10^7 secondes est une approximation incroyablement bonne du nombre de secondes dans une année, cela prendrait environ 6 mois à mon ordinateur.
Vous voudrez donc exécuter avec un algorithme approximatif.
