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行ずつメモリに保持するだけでよく、カウントもグラフよりもはるかに小さくなります。 。次数がわかれば、最大の連結成分を見つけるときにグラフから次数1の頂点を省略し、後で省略されたノードを修正できます。一般的なアルゴリズムを実装するのではなく、データ分析を行っています。より複雑な分析を可能にするために、データに関する簡単なことを学びます。

于 2011-11-24T09:45:35.270 に答える
5

ここにいくつかのアイデアがあります：

  1. 文字列の代わりに整数でノードに名前を付けることができます。これにより、質問のアプローチ（文字列を使用）と比較して、メモリを節約できます。

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

    実際、整数は、複数桁の識別子に対して、文字列よりもはるかに少ないメモリを使用します。

  2. オペレーティングシステムが単にスワッピングを開始するので、メモリがいっぱいになってもプログラムを実行させます。約3億のノードがあるので、数GBのメモリを使用する可能性があると思います。コンピュータがスワップした場合でも、その数のノードを処理できる可能性があります（特に、整数ラベルのノードを使用して節約されたメモリを使用）。

于 2011-11-24T08:50:48.677 に答える