Networkx slutar aldrig beräkna Betweenness centrality för 2 mil noder

TL/DR:Betweenness centrality är en mycket långsam beräkning, så du vill förmodligen använda ett ungefärligt mått genom att överväga en delmängd av myk noder där myk är ett antal mycket mindre än antalet noder i nätverket, men tillräckligt stort för att vara statistiskt meningsfullt (NetworkX har ett alternativ för detta:betweenness_centrality(G, k=myk) .

Jag är inte alls förvånad över att det tar lång tid. Centralitet mellan varandra är en långsam beräkning. Algoritmen som används av networkx är O(VE) där V är antalet hörn och E antalet kanter. I ditt fall VE = 10^13 . Jag förväntar mig att importen av grafen tar O(V+E) tid, så om det tar tillräckligt lång tid att du kan se att det inte är omedelbart, då O(VE) kommer att göra ont.

Om ett reducerat nätverk med 1 % av noderna och 1 % av kanterna (alltså 20 000 noder och 50 000 kanter) skulle ta tid X, så skulle din önskade beräkning ta 10 000X. Om X är en sekund så är den nya beräkningen nära 3 timmar, vilket jag tycker är otroligt optimistiskt (se mitt test nedan). Så innan du bestämmer dig för att det är något fel med din kod, kör den på några mindre nätverk och få en uppskattning av vad körtiden bör vara för ditt nätverk.

Ett bra alternativ är att använda ett ungefärligt mått. Standardmåttet mellanness tar hänsyn till varje enskilt par av noder och vägarna mellan dem. Networkx erbjuder ett alternativ som använder ett slumpmässigt urval av bara k noder och hittar sedan de kortaste vägarna mellan dessa k noder och alla andra noder i nätverket. Jag tror att detta borde ge en snabbare körning i O(kE) tid

Så det du skulle använda är

betweenness_centrality(G, k=k)

Om du vill ha gränser för hur exakt ditt resultat är, kan du göra flera samtal med ett litet värde på k , se till att de är relativt nära och ta sedan medelresultatet.

Här är några av mina snabba tester av körtid, med slumpmässiga grafer av (V,E)=(20,50); (200 500); och (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 dator tar det 15 sekunder att hantera ett nätverk som är 0,1 % av storleken på ditt. Det skulle ta cirka 15 miljoner sekunder att skapa ett nätverk av samma storlek som ditt. Det är 1,5*10^7 sekunder vilket är lite under hälften av pi*10^7 sekunder. Eftersom pi*10^7 sekunder är en otroligt bra uppskattning av antalet sekunder på ett år, skulle detta ta min dator cirka 6 månader.

Så du vill köra med en ungefärlig algoritm.