Networkx никогда не заканчивает вычисление Централь ности между двумя миллионами узлов



У меня есть простой график пользователей twitter с примерно 2 миллионами узлов и 5 миллионами ребер. Я пытаюсь играть с Центральностью. Однако расчет занимает действительно много времени (более часа). Я не считаю свой график слишком большим, поэтому предполагаю, что с моим кодом что-то не так.

Вот мой код.

%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)

Данные находятся в MongoDB. Вот образец данных.

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

Я пробовал использовать параллельность Централь-ности betweenness для ускорения, но это все еще очень медленно. 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("ttTime: %.4F" % (time.time()-start))
print("ttBetweenness centrality for node 0: %.5f" % (bt[0]))
Процесс импорта из Mongodb в networkx происходит относительно быстро, менее минуты.
157   1  

1 ответ:

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, то ваш желаемый расчет займет 10000x. если 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 секунд, что немного меньше половины Пи*10^7 секунд. Поскольку pi * 10^7 секунд-это невероятно хорошее приближение к числу секунд в году, это займет у моего компьютера около 6 месяцев.

Таким образом, вы захотите работать с приближенным алгоритмом.

    Ничего не найдено.

Добавить ответ:
Отменить.