Networkx nunca termina de calcular la centralidad de intermediación para nodos de 2 mil.

Tengo un gráfico simple de usuarios de Twitter con alrededor de 2 millones de nodos y 5 millones de bordes. Estoy tratando de jugar un poco con Centrality. Sin embargo, el cálculo tarda mucho tiempo (más de una hora). No considero que mi gráfico sea muy grande, así que supongo que podría haber algún problema con mi código.

Aquí está mi código.

%matplotlib inline import pymongo import networkx as nx import time import itertools from multiprocessing import Pool from pymongo import MongoClient from sweepy.get_config import get_config config = get_config() MONGO_URL = config.get('MONGO_URL') MONGO_PORT = config.get('MONGO_PORT') MONGO_USERNAME = config.get('MONGO_USERNAME') MONGO_PASSWORD = config.get('MONGO_PASSWORD') client = MongoClient(MONGO_URL, int(MONGO_PORT)) db = client.tweets db.authenticate(MONGO_USERNAME, MONGO_PASSWORD) users = db.users graph = nx.DiGraph() for user in users.find(): graph.add_node(user['id_str']) for friend_id in user['friends_ids']: if not friend_id in graph: graph.add_node(friend_id) graph.add_edge(user['id_str'], friend_id) 

Los datos están en MongoDB. Aquí está la muestra de datos.

 { "_id" : ObjectId("55e1e425dd232e5962bdfbdf"), "id_str" : "246483486", ... "friends_ids" : [ // a bunch of ids ] } 

Intenté usar la centralidad de intermediación paralela para acelerar, pero sigue siendo muy lento. https://networkx.github.io/documentation/latest/examples/advanced/parallel_betweenness.html

 """ Example of parallel implementation of betweenness centrality using the multiprocessing module from Python Standard Library. The function betweenness centrality accepts a bunch of nodes and computes the contribution of those nodes to the betweenness centrality of the whole network. Here we divide the network in chunks of nodes and we compute their contribution to the betweenness centrality of the whole network. """ def chunks(l, n): """Divide a list of nodes `l` in `n` chunks""" l_c = iter(l) while 1: x = tuple(itertools.islice(l_c, n)) if not x: return yield x def _betmap(G_normalized_weight_sources_tuple): """Pool for multiprocess only accepts functions with one argument. This function uses a tuple as its only argument. We use a named tuple for python 3 compatibility, and then unpack it when we send it to `betweenness_centrality_source` """ return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple) def betweenness_centrality_parallel(G, processes=None): """Parallel betweenness centrality function""" p = Pool(processes=processes) node_divisor = len(p._pool)*4 node_chunks = list(chunks(G.nodes(), int(G.order()/node_divisor))) num_chunks = len(node_chunks) bt_sc = p.map(_betmap, zip([G]*num_chunks, [True]*num_chunks, [None]*num_chunks, node_chunks)) # Reduce the partial solutions bt_c = bt_sc[0] for bt in bt_sc[1:]: for n in bt: bt_c[n] += bt[n] return bt_c print("Computing betweenness centrality for:") print(nx.info(graph)) start = time.time() bt = betweenness_centrality_parallel(graph, 2) print("\t\tTime: %.4F" % (time.time()-start)) print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0])) 

El proceso de importación de Mongodb a networkx es relativamente rápido, menos de un minuto.

TL / DR: la centralidad de la interrelación es un cálculo muy lento, por lo que es probable que desee utilizar una medida aproximada considerando un subconjunto de nodos myk 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ístico significativo (NetworkX tiene una opción para esto: betweenness_centrality(G, k=myk) .


No estoy en absoluto sorprendido de que esté tomando mucho tiempo. La centralidad de la 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 bordes. En tu caso VE = 10^13 . Espero que la importación de la gráfica tome el tiempo de O(V+E) , por lo que si se está demorando lo suficiente como para saber que no es instantáneo, entonces O(VE) 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 el tiempo X, entonces su cálculo deseado tomaría 10000X. Si X es un segundo, entonces el nuevo cálculo es cerca de 3 horas, lo que creo que es increíblemente optimista (vea mi prueba a continuación). Entonces, antes de decidir que hay algo mal 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 las rutas 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 tiempo O(kE)

Así que 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 de k pequeño, asegúrese de que estén relativamente cerca y luego tome el resultado promedio.


Aquí están 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 

Entonces, en mi computadora, toma 15 segundos manejar una red que es 0.1% su tamaño. Tomaría aproximadamente 15 millones de segundos hacer una red del mismo tamaño que la tuya. Eso es 1.5 * 10 ^ 7 segundos, que es un poco menos de la mitad de pi * 10 ^ 7 segundos. Ya que pi * 10 ^ 7 segundos es una aproximación increíblemente buena a la cantidad de segundos en un año, esto llevaría a mi computadora aproximadamente 6 meses.

Así que querrás correr con un algoritmo aproximado.