4

我编写了一个代码来生成具有 379613734 条边的图形。

但是由于内存原因，代码无法完成。当它通过 6200 万行时，它会占用大约 97% 的服务器内存。所以我杀了它。

你有解决这个问题的想法吗？

我的代码是这样的：

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

边缘数据是这样的：

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

最后，有没有人有分析 Twitter 链接数据的经验？我很难采用有向图并计算节点的平均/中值入度和出度。有什么帮助或想法吗？

4

2 回答 2

7

首先，您应该考虑是否可以添加更多 RAM。通过根据您拥有的数据进行计算或通过读取各种大小的数据的子样本来衡量事物的扩展方式，对内存使用情况进行一些估计。几 GB RAM 的适度成本可能会为您节省大量时间和麻烦。

其次，考虑是否需要实际构建整个图。例如，您可以通过遍历文件并计数来确定顶点的数量及其度数 - 您只需在内存中一次保留一行，加上计数，这将比图表小得多. 知道度数后，您可以在找到最大连通分量时从图中省略任何度数为 1 的顶点，然后对省略的节点进行校正。您正在进行数据分析，而不是实现一些通用算法：了解有关数据的简单信息以进行更复杂的分析。

于 2011-11-24T09:45:35.270 回答
5

这里有一些想法：

  1. 您可以用整数而不是字符串命名节点：与问题中的方法（使用字符串）相比，这将节省内存：

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

    事实上，对于多位标识符，整数比字符串占用的内存要少得多。

  2. 即使内存已满也让程序运行，因为您的操作系统将简单地开始交换：您有大约 3 亿个节点，所以我猜它们可能会占用几 GB 的内存；即使您的计算机交换，它也可能能够处理那么多节点（尤其是使用整数标记节点节省的内存）。

于 2011-11-24T08:50:48.677 回答