Pythonで最も効率的なグラフデータ構造は何ですか？

Question

私は大きな（10^7ノード）グラフをPythonで操作できる必要があります。各ノード/エッジに対応するデータは最小であり、例えば少数のストリングである。 メモリと速度の面で最も効率的なものは何ですか、、これを行う方法？

dictsのdictはより柔軟で実装が簡単ですが、私は直感的にリストのリストがより速くなることを期待しています。

graph[I][J]["Property"]="value" 

あなたは何を示唆している：リストのオプションは、私はdictsソートの何かを可能にする一方で、構造体から分離したデータを保持することも必要でしょうか？

---

はい、私は効率がどういう意味であるかを少しはっきりさせていたはずです。この特定のケースでは、私はランダムアクセス検索の点でそれを意味します。

データをメモリにロードすることは大きな問題ではありません。それは一度だけで済んでいます。時間がかかる部分はノードを訪問しているので、私が情報を抽出し、私が興味を持っているメトリクスを測定することができます。

私は各ノードをクラスにすることは考えていませんでした（プロパティはすべてのノードで同じ）そのようなオーバーヘッドの余分な層を追加しますか？誰かが分かち合うことができる同様のケースで直接体験してもらいたいと思っていました。結局のところ、グラフはCSの最も一般的な抽象化の1つです。

Answer 1

NetworkXを強く主張します。これは戦闘テスト済みの戦争馬であり、ネットワークベースのデータの分析を行う必要がある場合、ほとんどの「リサーチ」タイプに到達する最初のツールです。私はノートブックで問題なく100万のエッジでグラフを操作しました。豊富で使いやすい機能です。基本的な実装の詳細ではなく、手元の問題にもっと集中しています。

Erdős-Rényiランダムグラフ生成の実施例及び分析

""" 
Create an G{n,m} random graph with n nodes and m edges 
and report some properties. 

This graph is sometimes called the Erd##[m~Qs-Rényi graph 
but is different from G{n,p} or binomial_graph which is also 
sometimes called the Erd##[m~Qs-Rényi graph. 
""" 
__author__ = """Aric Hagberg (hagberg@lanl.gov)""" 
__credits__ = """""" 
# Copyright (C) 2004-2006 by 
# Aric Hagberg 
# Dan Schult 
# Pieter Swart 
# Distributed under the terms of the GNU Lesser General Public License 
# http://www.gnu.org/copyleft/lesser.html 

from networkx import * 
import sys 

n=10 # 10 nodes 
m=20 # 20 edges 

G=gnm_random_graph(n,m) 

# some properties 
print "node degree clustering" 
for v in nodes(G): 
    print v,degree(G,v),clustering(G,v) 

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout) 

視覚化も簡単である：

可視詳細：既に述べたようにhttp://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 2

辞書には実際の実装に応じてオーバーヘッドが含まれることもあります。ハッシュテーブルには、通常、いくつかのノードを使用する場合でも、いくつかの素数の使用可能なノードが含まれています。

あなたの例で判断すると、「プロパティ」は、最終的なレベルと実際のプロパティのクラスアプローチの方がよいでしょうか？あるいは、プロパティーの名前がノードからノードに大きく変化していますか？私が何を「効率的」を意味するように、多くのものに依存していることを言うだろう

：

• の更新の速さ（挿入、更新、削除）
• ランダム・アクセス・検索
• の速度順次検索の速度
• メモリは、私はあなたがなり、一般的に、Cスピーディーであるというデータ構造を見つけることだと思う

を使用しました遅いものよりもメモリが多い。これは必ずしも当てはまるわけではありませんが、ほとんどのデータ構造はこれに従っているようです。

辞書は使いやすく、比較的均一に高速なアクセスを提供しますが、リストのように多くのメモリを使用する可能性が高くなります。しかし、リストには、Xノードを事前に割り当てない限り、データを挿入するときにオーバーヘッドが多くなる傾向があります。

私の提案は、一般的には、あなたにとって最も自然に思える方法を使用してシステムの「ストレステスト」を行い、かなりの量のデータを追加し、問題。

抽象レイヤーをシステムに追加することも考えられます。後で内部データ構造を変更する必要がある場合は、プログラミングインターフェースを変更する必要はありません。

Answer 3

クラスベースの構造を作成すると、おそらくPythonクラスで実装されたときにdictsを使用するため、dictベースの構造よりもオーバーヘッドが大きくなります。

Answer 4

私が理解しているように、ランダムアクセスはPythonのdictsとリストの両方に対して一定の時間がありますが、違いはリストで整数インデックスをランダムアクセスできることです。私はあなたがそのラベルでノードを検索する必要があると仮定しているので、あなたはdictsのdictを望んでいます。

しかしパフォーマンスフロントでは、メモリにロードすることは問題ではないかもしれませんが、あまりにも多く使うとディスクにスワップすることになり、Pythonの非常に効率的なdictsのパフォーマンスも低下します。可能な限りメモリ使用量を抑えてください。また、RAMは驚くほど安いです。あなたがこの種のことをたくさんしているなら、少なくとも4GBを持っていない理由はありません。

メモリ使用量を抑えるためのアドバイスが必要な場合は、ノードごとにトラッキングしている情報の種類についていくつかの情報を提供してください。

Answer 5

、NetworkXは非常にあります行くod、別のオプションはigraphです。どちらのモジュールも、必要と思われる分析ツールのほとんど（すべてではないにしても）を持ち、両方のライブラリは大規模なネットワークで日常的に使用されます。

Answer 6

この質問はかなり古くなっていますが、graph-toolと呼ばれるグラフ操作用の独自のPythonモジュールについて言及することは有益です。 Boost Graph Libraryを使用すると、データ構造とアルゴリズムがC++で実装されているため、テンプレートのメタプログラミングを使用すると非常に効率的です。したがって、そのパフォーマンス（メモリ使用量とランタイムの両方）は、純粋なC++ライブラリに匹敵し、使いやすさを犠牲にすることなく、典型的なPythonコードよりもはるかに優れています。私は非常に大きなグラフを扱うために自分自身を常に使用しています。

Answer 7

間違いなくNetworkXは今までのグラフにとって最高のデータ構造です。ヘルパー関数、データ構造とアルゴリズム、ランダムシーケンスジェネレータ、デコレータ、Cuthill-Mckee Ordering、コンテキストマネージャのようなユーティリティが付属しています。

NetworkXはグラフ、ダイグラフ、マルチグラフに威力を発揮します。隣接リスト、複数行隣接リスト、 エッジリスト、GEXF、GMLなど、複数の方法でグラフを書くことができます。 Pickle、GraphML、JSON、SparseGraph6などで動作します。

それが含む様々なradimadeアルゴリズムのimplimentationあり： 近似、二部、境界、中心性、クリーク、クラスタリング、着色、コンポーネント、接続、サイクル、無閉路有向グラフ、 距離尺度、支配集合問題、オイラー、同型、リンク分析、リンク予測、マッチング、最小スパニングツリー、リッチクラブ、最短パス、トラバーサル、ツリー。