TL/DR:Centralność pomiędzy jest bardzo powolnym obliczeniem, więc prawdopodobnie chcesz użyć przybliżonej miary, biorąc pod uwagę podzbiór myk węzły, w których myk to pewna liczba znacznie mniejsza niż liczba węzłów w sieci, ale wystarczająco duża, aby była istotna statystycznie (NetworkX ma taką opcję:betweenness_centrality(G, k=myk) .
Wcale mnie to nie dziwi, że zajmuje to dużo czasu. Centralność pomiędzy jest powolną kalkulacją. Algorytm używany przez networkx to O(VE) gdzie V to liczba wierzchołków i E liczba krawędzi. W Twoim przypadku VE = 10^13 . Spodziewam się, że importowanie wykresu zajmie O(V+E) czas, więc jeśli zajmuje to wystarczająco dużo czasu, aby można było stwierdzić, że nie jest natychmiastowe, wtedy O(VE) będzie bolesne.
Jeśli zredukowana sieć z 1% węzłów i 1% krawędzi (czyli 20 000 węzłów i 50 000 krawędzi) zajęłaby czas X, to pożądane obliczenie zajęłoby 10000X. Jeśli X to jedna sekunda, to nowe obliczenia są bliskie 3 godzinom, co moim zdaniem jest niesamowicie optymistyczne (patrz mój test poniżej). Więc zanim zdecydujesz, że coś jest nie tak z twoim kodem, uruchom go w kilku mniejszych sieciach i uzyskaj oszacowanie, jaki powinien być czas działania dla twojej sieci.
Dobrą alternatywą jest użycie miary przybliżonej. Standardowa miara odległości uwzględnia każdą pojedynczą parę węzłów i ścieżki między nimi. Networkx oferuje alternatywę, która wykorzystuje losową próbkę zaledwie k węzłów, a następnie znajduje najkrótsze ścieżki między tymi k węzły i wszystkie inne węzły w sieci. Myślę, że powinno to przyspieszyć działanie w O(kE) czas
Więc to, czego użyjesz, to
betweenness_centrality(G, k=k)
Jeśli chcesz mieć granice dokładności wyniku, możesz wykonać kilka wywołań z niewielką wartością k , upewnij się, że są stosunkowo blisko, a następnie weź średni wynik.
Oto niektóre z moich szybkich testów czasu działania, z losowymi wykresami (V,E)=(20,50); (200500); i (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 więc na moim komputerze obsługa sieci, która jest o 0,1% większa od twojej, zajmuje 15 sekund. Wykonanie sieci o takim samym rozmiarze jak twoja zajęłoby około 15 milionów sekund. To 1,5*10^7 sekund, czyli nieco mniej niż połowa pi*10^7 sekund. Ponieważ pi*10^7 sekund to niewiarygodnie dobre przybliżenie liczby sekund w roku, zajęłoby to mojemu komputerowi około 6 miesięcy.
Więc będziesz chciał uruchomić z przybliżonym algorytmem.
