Проблемы с памятью во время работы кода (Python, Networkx)

Question

Я создал код для генерации графа с 379613734 ребрами.

Но код не мог быть завершен из-за памяти.Он занимает около 97% серверной памяти, когда проходит через 62 миллиона строк.Итак, я убил его.

У вас есть идеи, чтобы решить эту проблему?

Мой код такой:

import os, sys
import time
import networkx as nx


G = nx.Graph()

ptime = time.time()
j = 1

for line in open("./US_Health_Links.txt", 'r'):
#for line in open("./test_network.txt", 'r'):
    follower = line.strip().split()[0]
    followee = line.strip().split()[1]

    G.add_edge(follower, followee)

    if j%1000000 == 0:
        print j*1.0/1000000, "million lines done", time.time() - ptime
        ptime = time.time()
    j += 1

DG = G.to_directed()
#       P = nx.path_graph(DG)
Nn_G = G.number_of_nodes()
N_CC = nx.number_connected_components(G)
LCC = nx.connected_component_subgraphs(G)[0]
n_LCC = LCC.nodes()
Nn_LCC = LCC.number_of_nodes()
inDegree = DG.in_degree()
outDegree = DG.out_degree()
Density = nx.density(G)
#       Diameter = nx.diameter(G)
#       Centrality = nx.betweenness_centrality(PDG, normalized=True, weighted_edges=False)
#       Clustering = nx.average_clustering(G)

print "number of nodes in G\t" + str(Nn_G) + '\n' + "number of CC in G\t" + str(N_CC) + '\n' + "number of nodes in LCC\t" + str(Nn_LCC) + '\n' + "Density of G\t" + str(Density) + '\n'
#       sys.exit()
#   j += 1

Данные о границах таковы:1010 *

1000    1001
1000245    1020191
1000    10267352
1000653    10957902
1000    11039092
1000    1118691
10346    11882
1000    1228281
1000    1247041
1000    12965332
121340    13027572
1000    13075072
1000    13183162
1000    13250162
1214    13326292
1000    13452672
1000    13844892
1000    14061830
12340    1406481
1000    14134703
1000    14216951
1000    14254402
12134   14258044
1000    14270791
1000    14278978
12134    14313332
1000    14392970
1000    14441172
1000    14497568
1000    14502775
1000    14595635
1000    14620544
1000    14632615
10234    14680596
1000    14956164
10230    14998341
112000    15132211
1000    15145450
100    15285998
1000    15288974
1000    15300187
1000    1532061
1000    15326300

Наконец, есть кто-нибудь, у кого есть опыт для анализа данных ссылок в Твиттере?Мне довольно сложно взять ориентированный граф и рассчитать среднюю / среднюю степень и степень узлов.Любая помощь или идея?

Answer 1

Во-первых, вы должны подумать, можете ли вы просто добавить больше оперативной памяти. Сделайте некоторые оценки использования памяти, либо рассчитывая на основе имеющихся у вас данных, либо читая в подвыборках данных различного размера, чтобы измерить, как все масштабируется. Скромная стоимость нескольких ГБ ОЗУ может сэкономить вам много времени и хлопот.

Во-вторых, подумайте, нужно ли вам на самом деле построить весь график. Например, вы можете определить количество вершин и их градусы, просто перебирая файл и подсчитывая - вам нужно будет хранить только одну строку за раз в памяти плюс количество, которое будет намного меньше, чем график , Зная градусы, вы можете опустить любые вершины с градусом один из графа при поиске наибольшего связанного компонента, а затем исправить для пропущенных узлов. Вы делаете анализ данных, а не реализуете какой-то общий алгоритм: изучите простые вещи о данных, чтобы сделать возможным более сложный анализ.

Answer 2

Вот несколько идей:

1. Вы можете называть свои узлы целыми числами вместо строк: это сэкономит память по сравнению с подходом в вопросе (который использует строки):

   follower, followee = map(int, line.split())
   

   Фактически, целые числа занимают намного меньше памяти, чем строки, для многозначных идентификаторов.

2. Дайте программе работать даже если память заполнится, ваша операционная система просто начнет подкачку: у вас около 300 миллионов узлов, поэтому я думаю, что они могут занять несколько ГБ памяти;даже если ваш компьютер меняет местами, он может обрабатывать такое количество узлов (особенно с помощью памяти, сохраненной с помощью целочисленных узлов).