TL/DR:Централността на междуличността е много бавно изчисление, така че вероятно искате да използвате приблизителна мярка, като вземете предвид подмножество от myk възли, където myk е някакво число, много по-малко от броя на възлите в мрежата, но достатъчно голямо, за да бъде статистически значимо (NetworkX има опция за това:betweenness_centrality(G, k=myk) .
Изобщо не съм изненадан, че отнема много време. Междуцентралността е бавно изчисление. Алгоритъмът, използван от networkx, е O(VE) където V е броят на върховете и E броя на ръбовете. Във вашия случай VE = 10^13 . Очаквам импортирането на графиката да отнеме O(V+E) време, така че ако това отнема достатъчно време, за да можете да разберете, че не е моментално, тогава O(VE) ще бъде болезнено.
Ако намалена мрежа с 1% от възлите и 1% от ръбовете (така че 20 000 възела и 50 000 ръба) ще отнеме време X, тогава желаното от вас изчисление ще отнеме 10 000X. Ако X е една секунда, тогава новото изчисление е близо до 3 часа, което според мен е невероятно оптимистично (вижте моя тест по-долу). Така че, преди да решите, че нещо не е наред с вашия код, изпълнете го в някои по-малки мрежи и получете оценка какво трябва да бъде времето за изпълнение за вашата мрежа.
Добра алтернатива е да използвате приблизителна мярка. Стандартната мярка за междуличност разглежда всяка отделна двойка възли и пътищата между тях. Networkx предлага алтернатива, която използва произволна извадка от само k възли и след това намира най-кратките пътища между тези k възли и всички други възли в мрежата. Мисля, че това трябва да ускори работата в O(kE) време
Така че това, което бихте използвали, е
betweenness_centrality(G, k=k)
Ако искате да имате граници за това колко точен е вашият резултат, можете да направите няколко извиквания с малка стойност от k , уверете се, че са относително близки и след това вземете средния резултат.
Ето някои от моите бързи тестове на времето за изпълнение, със произволни графики на (V,E)=(20,50); (200 500); и (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
Така че на моя компютър са необходими 15 секунди, за да се справя с мрежа, която е 0,1% от размера на вашия. Ще са необходими около 15 милиона секунди, за да направите мрежа със същия размер като вашата. Това е 1,5*10^7 секунди, което е малко под половината от pi*10^7 секунди. Тъй като pi*10^7 секунди е невероятно добро приближение към броя секунди за една година, това ще отнеме на компютъра ми около 6 месеца.
Така че ще искате да стартирате с приблизителен алгоритъм.
