TL/DR:Mellemliggende centralitet er en meget langsom beregning, så du vil sandsynligvis bruge et omtrentligt mål ved at overveje en delmængde af myk noder hvor myk er et eller andet tal meget mindre end antallet af noder i netværket, men stort nok til at være statistisk meningsfuldt (NetworkX har en mulighed for dette:betweenness_centrality(G, k=myk) .
Jeg er slet ikke overrasket over, at det tager lang tid. Mellemliggende centralitet er en langsom beregning. Algoritmen brugt af networkx er O(VE) hvor V er antallet af hjørner og E antallet af kanter. I dit tilfælde VE = 10^13 . Jeg forventer, at import af grafen tager O(V+E) tid, så hvis det tager lang tid nok til, at du kan se, at det ikke er øjeblikkeligt, så O(VE) vil være smertefuldt.
Hvis et reduceret netværk med 1% af noderne og 1% af kanterne (altså 20.000 noder og 50.000 kanter) ville tage tid X, så ville din ønskede beregning tage 10000X. Hvis X er et sekund, så er den nye udregning tæt på 3 timer, hvilket jeg synes er utrolig optimistisk (se min test nedenfor). Så før du beslutter dig for, at der er noget galt med din kode, så kør den på nogle mindre netværk og få et skøn over, hvad køretiden skal være for dit netværk.
Et godt alternativ er at bruge et omtrentligt mål. Standardmålet mellemhed tager hensyn til hvert enkelt par af noder og stierne mellem dem. Networkx tilbyder et alternativ, som bruger en tilfældig prøve på kun k noder og finder derefter den korteste vej mellem disse k noder og alle andre noder i netværket. Jeg tror, at dette burde give en speedup til at køre i O(kE) tid
Så hvad du ville bruge er
betweenness_centrality(G, k=k)
Hvis du vil have grænser for, hvor nøjagtigt dit resultat er, kan du foretage flere opkald med en lille værdi på k , sørg for, at de er relativt tæt på, og tag derefter gennemsnitsresultatet.
Her er nogle af mine hurtige test af køretid, med tilfældige grafer af (V,E)=(20,50); (200.500); og (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
Så på min computer tager det 15 sekunder at håndtere et netværk, der er 0,1 % af størrelsen på dit. Det ville tage omkring 15 millioner sekunder at lave et netværk af samme størrelse som dit. Det er 1,5*10^7 sekunder, hvilket er lidt under halvdelen af pi*10^7 sekunder. Da pi*10^7 sekunder er en utrolig god tilnærmelse til antallet af sekunder på et år, ville det tage min computer omkring 6 måneder.
Så du vil gerne køre med en omtrentlig algoritme.