python - 1億ノードのグラフの連結成分

Question

1億ノードのグラフで連結成分のリストを取得しようとしています。小さいグラフの場合、私は通常、PythonのNetworkxモジュールのconnected_components関数を使用します。これはまさにそれを実行します。ただし、このモジュールを使用して1億ノード（およびそのエッジ）を含むグラフをメモリにロードするには、約1億が必要です。私が持っていない110GBのメモリ。別の方法は、連結成分関数を持つグラフデータベースを使用することですが、Pythonでは何も見つかりませんでした。Dex（API：Java、.NET、C ++）にはこの機能があるように見えますが、100％確信はありません。理想的には、Pythonでの解決策を探しています。どうもありがとう。

Answer 1

SciPy には、連結成分アルゴリズムがあります。入力としてグラフの隣接行列をスパース行列形式の 1 つとして想定し、有向と無向の両方のケースを処理します。

とがノードの (0 ベースの) インデックスである一連の(i, j)ペアから疎な隣接行列を構築するには、次のコマンドを使用します。adj_listij

i_indices, j_indices = zip(*adj_list)
adj_matrix = scipy.sparse.coo_matrix((np.ones(number_of_nodes),
                                     (i_indices, j_indices)))

無向の場合には、追加の作業を行う必要があります。

グラフが十分にまばらな場合、このアプローチは効率的です。

Answer 2

https://graph-tool.skewed.de/performance

パフォーマンスからわかるように、このツールは非常に高速です。C++ で書かれていますが、インターフェースは Python です。

このツールが十分でない場合。（そうなると思います）それからApache Giraph（http://giraph.apache.org/）を試すことができます。