TL/DR:La centralità di Betweenness è un calcolo molto lento, quindi probabilmente vorrai utilizzare una misura approssimativa considerando un sottoinsieme di myk nodi dove myk è un numero molto inferiore al numero di nodi nella rete, ma abbastanza grande da essere statisticamente significativo (NetworkX ha un'opzione per questo:betweenness_centrality(G, k=myk) .
Non sono affatto sorpreso che stia impiegando molto tempo. La centralità di Betweenness è un calcolo lento. L'algoritmo utilizzato da networkx è O(VE) dove V è il numero di vertici e E il numero di bordi. Nel tuo caso VE = 10^13 . Mi aspetto che l'importazione del grafico prenda O(V+E) tempo, quindi se ci vuole abbastanza tempo per capire che non è istantaneo, allora O(VE) sarà doloroso.
Se una rete ridotta con l'1% dei nodi e l'1% dei bordi (quindi 20.000 nodi e 50.000 bordi) richiedesse tempo X, il calcolo desiderato richiederebbe 10000 volte. Se X è un secondo, il nuovo calcolo è vicino a 3 ore, il che penso sia incredibilmente ottimistico (vedi il mio test di seguito). Quindi, prima di decidere che c'è qualcosa di sbagliato nel tuo codice, eseguilo su alcune reti più piccole e ottieni una stima di quale dovrebbe essere il tempo di esecuzione per la tua rete.
Una buona alternativa è usare una misura approssimativa. La misura di interconnessione standard considera ogni singola coppia di nodi e i percorsi tra di loro. Networkx offre un'alternativa che utilizza un campione casuale di solo k nodi e quindi trova i percorsi più brevi tra quei k nodi e tutti gli altri nodi della rete. Penso che questo dovrebbe accelerare l'esecuzione in O(kE) tempo
Quindi quello che useresti è
betweenness_centrality(G, k=k)
Se vuoi avere limiti su quanto sia accurato il tuo risultato, puoi fare diverse chiamate con un valore piccolo di k , assicurati che siano relativamente vicini e poi prendi il risultato medio.
Ecco alcuni dei miei rapidi test del tempo di esecuzione, con grafici casuali di (V,E)=(20,50); (200.500); e (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
Quindi sul mio computer ci vogliono 15 secondi per gestire una rete che ha una dimensione dello 0,1% della tua. Ci vorrebbero circa 15 milioni di secondi per creare una rete delle stesse dimensioni della tua. Sono 1,5*10^7 secondi che è poco meno della metà di pi*10^7 secondi. Poiché pi*10^7 secondi è un'approssimazione incredibilmente buona del numero di secondi in un anno, il mio computer impiegherebbe circa 6 mesi.
Quindi ti consigliamo di eseguire con un algoritmo approssimativo.
