Networkx nikdy nedokončí výpočet centrality Betweenness pro 2 miliony uzlů

TL/DR:Centralita mezi jednotlivými hodnotami je velmi pomalý výpočet, takže pravděpodobně budete chtít použít přibližnou míru s ohledem na podmnožinu myk uzly kde myk je nějaké číslo mnohem menší než počet uzlů v síti, ale dostatečně velké na to, aby to bylo statisticky vypovídající (NetworkX má pro toto možnost:betweenness_centrality(G, k=myk) .

Vůbec se nedivím, že to trvá dlouho. Centralita mezi mezistvy je pomalý výpočet. Algoritmus používaný networkx je O(VE) kde V je počet vrcholů a E počet hran. Ve vašem případě VE = 10^13 . Očekávám, že import grafu bude trvat O(V+E) čas, takže pokud to trvá dostatečně dlouho, abyste mohli říct, že to není okamžité, pak O(VE) bude to bolestivé.

Pokud by redukovaná síť s 1 % uzlů a 1 % hran (takže 20 000 uzlů a 50 000 hran) zabrala čas X, pak by požadovaný výpočet trval 10 000X. Pokud je X jedna sekunda, pak se nový výpočet blíží 3 hodinám, což je podle mě neuvěřitelně optimistické (viz můj test níže). Než se tedy rozhodnete, že je s vaším kódem něco v nepořádku, spusťte jej v některých menších sítích a získejte odhad, jaká by měla být doba běhu vaší sítě.

Dobrou alternativou je použití přibližné míry. Standardní míra mezilehlosti zohledňuje každý jednotlivý pár uzlů a cesty mezi nimi. Networkx nabízí alternativu, která používá náhodný vzorek pouze k uzly a poté najde nejkratší cesty mezi těmito k uzly a všechny ostatní uzly v síti. Myslím, že by to mělo urychlit běh v O(kE) čas

Takže to, co byste použili, je

betweenness_centrality(G, k=k)

Pokud chcete mít hranice přesnosti vašeho výsledku, můžete provést několik volání s menší hodnotou k , ujistěte se, že jsou relativně blízko, a poté vezměte průměrný výsledek.

Zde je několik mých rychlých testů doby běhu s náhodnými grafy (V,E)=(20,50); (200 500); a (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

Takže na mém počítači trvá 15 sekund, než zvládnu síť o velikosti 0,1 % té vaší. Vytvoření sítě stejné velikosti, jako je ta vaše, by trvalo asi 15 milionů sekund. To je 1,5*10^7 sekund, což je o něco méně než polovina pi*10^7 sekund. Protože pi*10^7 sekund je neuvěřitelně dobrá aproximace počtu sekund za rok, trvalo by to mému počítači asi 6 měsíců.

Takže budete chtít spustit s přibližným algoritmem.