TL/DR:A centralidade de intermediação é um cálculo muito lento, então você provavelmente deseja usar uma medida aproximada considerando um subconjunto de
myk nós onde myk é um número muito menor que o número de nós na rede, mas grande o suficiente para ser estatisticamente significativo (NetworkX tem uma opção para isso:betweenness_centrality(G, k=myk) . Não estou surpreso que esteja demorando muito. A centralidade de intermediação é um cálculo lento. O algoritmo usado pelo networkx é
O(VE) onde V é o número de vértices e E o número de arestas. No seu caso VE = 10^13 . Espero importar o gráfico para levar O(V+E) tempo, então se isso está demorando o suficiente para que você possa dizer que não é instantâneo, então O(VE) vai ser doloroso. Se uma rede reduzida com 1% dos nós e 1% das arestas (portanto, 20.000 nós e 50.000 arestas) levaria um tempo X, o cálculo desejado levaria 10.000X. Se X é um segundo, então o novo cálculo é próximo de 3 horas, o que eu acho incrivelmente otimista (veja meu teste abaixo). Portanto, antes de decidir que há algo errado com seu código, execute-o em algumas redes menores e obtenha uma estimativa de qual deve ser o tempo de execução para sua rede.
Uma boa alternativa é usar uma medida aproximada. A medida de intermediação padrão considera cada par de nós e os caminhos entre eles. Networkx oferece uma alternativa que usa uma amostra aleatória de apenas
k nós e, em seguida, encontra os caminhos mais curtos entre esses k nós e todos os outros nós da rede. Eu acho que isso deve dar uma aceleração para rodar em O(kE) Tempo Então o que você usaria é
betweenness_centrality(G, k=k)
Se você quiser ter limites sobre a precisão do seu resultado, você pode fazer várias chamadas com um valor pequeno de
k , verifique se eles estão relativamente próximos e, em seguida, obtenha o resultado médio. Aqui estão alguns dos meus testes rápidos de tempo de execução, com gráficos aleatórios de (V,E)=(20,50); (200.500); e (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
Então, no meu computador, leva 15 segundos para lidar com uma rede que é 0,1% do tamanho da sua. Levaria cerca de 15 milhões de segundos para fazer uma rede do mesmo tamanho que a sua. Isso é 1,5*10^7 segundos, que é um pouco menos da metade de pi*10^7 segundos. Como pi*10^7 segundos é uma aproximação incrivelmente boa para o número de segundos em um ano, isso levaria cerca de 6 meses para o meu computador.
Então você vai querer executar com um algoritmo aproximado.
