大規模グラフ処理フレームワーク Pregel のオープンソース実装 Bagel とか - Standard ML of Yukkuri
ref: http://portal.acm.org/citation.cfm?id=1582723大規模グラフ処理フレームワーク Pregel の論文を読み, BSP (Bulk Synchronous Parallel) モデルで実装したいグラフのアルゴリズムがいくつかあったのでオープンソース実装を探してみた. GoldenOrb, Phoebus, HAMA (汎用的なBSP model), そして Bagel などいくつかの実装があるようで, GoldenOrb は Java, Phoebus は Erlang で実装されており, Bagel は Scala で書かれている. Bagel は Spark 上で動くシンプルな実装 (たったの 150 行程度) で, 大規模なタスクに対してもスケールする運用が可能に思えたので Bagel を使ってみることにした. (Phoebus は
Python でグラフ・(疎)行列計算するためのライブラリを紹介するよ - 武蔵野日記
PageRank とか HITS といったリンク解析ではグラフの計算が頻発するのだが、Python でそのあたり書くときの話をまとめてみる。グラフは行列で表現できる(ノード×ノード次元の行列 A を考えて、ノード i からノード j にエッジがあるとき、A[i,j] に値を入れておけばよい。無向グラフのときは A[i,j] = A[j,i] なので対称行列になる)ので、要は行列を手軽に扱えるライブラリの紹介である。 実は Python の行列演算ライブラリはどれも lapack/blas を内部的に呼んでいるので、C/C++ 等と比較してもそんなに遅くない。それどころか、自動的に並列化できるところは並列化してくれたりするので、まれに C より速いこともあるらしい。特に巨大なグラフを作る場合、ほとんどの処理は C などで書かれた関数に飛ぶので、速度的な問題は無視してもいいくらいである(逆に、
グラフライブラリ
グラフを扱うためのオープンなクラスライブラリにはBGL(Boost Graph Library)を筆頭に優れたものがたくさんありますが，本ライブラリは 導入が容易：簡単な機能は簡単に記述できること． カスタマイズが容易：ソースコードの一覧性が高いこと． ソコソコの機能でソレナリのパフォーマンス という点を目標に作成しています．特徴は以下の通りです． ノードとエッジの追加（定数時間） ノードとエッジへのインデクスを用いたランダムアクセス（定数時間） 任意のノードとエッジの削除（定数時間） ノードに隣接するノード群とその接続を媒介するエッジ群へのランダムアクセス（定数時間） ノードに隣接する特定のノード，あるいはエッジの検索（線形時間） エッジの両端に接続するノードの検索（定数時間） 有向グラフとして動作（無向グラフとしての利用も可能） 自己ループエッジ（両端が同一ノードのエッジ）と多重エッジ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
