TL/DR:la centralidad de intermediación es un cálculo muy lento, por lo que probablemente desee utilizar una medida aproximada considerando un subconjunto de myk nodos donde myk es un número mucho menor que el número de nodos en la red, pero lo suficientemente grande como para ser estadísticamente significativo (NetworkX tiene una opción para esto:betweenness_centrality(G, k=myk) .
No me sorprende en absoluto que esté tardando mucho. La centralidad de intermediación es un cálculo lento. El algoritmo utilizado por networkx es O(VE) donde V es el número de vértices y E el número de aristas. En tu caso VE = 10^13 . Espero importar el gráfico para tomar O(V+E) tiempo, por lo que si tarda lo suficiente como para darse cuenta de que no es instantáneo, entonces O(VE) va a ser doloroso.
Si una red reducida con el 1 % de los nodos y el 1 % de los bordes (por lo tanto, 20 000 nodos y 50 000 bordes) tomaría un tiempo X, entonces su cálculo deseado tomaría 10000X. Si X es un segundo, entonces el nuevo cálculo es cercano a las 3 horas, lo que creo que es increíblemente optimista (vea mi prueba a continuación). Entonces, antes de que decida que hay algún problema con su código, ejecútelo en algunas redes más pequeñas y obtenga una estimación de cuál debería ser el tiempo de ejecución para su red.
Una buena alternativa es utilizar una medida aproximada. La medida de intermediación estándar considera cada par de nodos y los caminos entre ellos. Networkx ofrece una alternativa que utiliza una muestra aleatoria de solo k nodos y luego encuentra las rutas más cortas entre esos k nodos y todos los demás nodos de la red. Creo que esto debería dar una aceleración para ejecutarse en O(kE) tiempo
Entonces, lo que usarías es
betweenness_centrality(G, k=k)
Si desea tener límites sobre la precisión de su resultado, puede hacer varias llamadas con un valor pequeño de k , asegúrese de que estén relativamente cerca y luego tome el resultado promedio.
Estas son algunas de mis pruebas rápidas de tiempo de ejecución, con gráficos aleatorios de (V,E)=(20,50); (200.500); y (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
Así que en mi computadora toma 15 segundos manejar una red que es 0.1% del tamaño de la suya. Tomaría alrededor de 15 millones de segundos hacer una red del mismo tamaño que la suya. Eso es 1,5*10^7 segundos, que es un poco menos de la mitad de pi*10^7 segundos. Dado que pi*10^7 segundos es una aproximación increíblemente buena a la cantidad de segundos en un año, mi computadora tardaría unos 6 meses.
Así que querrá ejecutar con un algoritmo aproximado.
