ラベル IncrementalGraph の投稿を表示しています。 すべての投稿を表示
ラベル IncrementalGraph の投稿を表示しています。 すべての投稿を表示

2011年8月3日水曜日

ぱーてぃしょにんぐ、しらべもの

Spectral Clusteringについて

Data Similarity Graphというグラフを定義し、そのグラフを対象とした話。
密行列なのでBSPやGIM-Vに向かない?
他のGraph Partitioningアルゴリズムを考えるべきかも。

勘違いしてるかも。

参考文献、URL
・d.hatena.ne.jp/mamoruk/20090128/p1
・Qianjun Xu, Marie desJardins and Kiri L. Wagstaff. Active Constrained Clustering by Examining Spectral Eigenvectors. Proc of Discovery Science 2005.
・・(2章)

今後

調べるアルゴリズム(アプリケーション)
・最短経路問題
・中心性解析 (Between Centrality)
・Random Walk with Restart
・Spectral Clustering (Graph Partitioning)

モデルとして、GIM-Vでなければならなかった理由?
・特になし。しいて言えば、PEGASUSがオープンソースだったから。
・Pregel,BagelなどのBSPでもいいと思う。実装コストはともかく

2011年4月25日月曜日

IGIMV (DE版) バグ?

snk_managerに謎の出力が入る.バイナリファイル扱いされる.
stop_stream せずに連続して submit_stream cancel_stream を繰り返していると生じる?
igimv の方ではなく,gimv の方で生じている?

see:
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-3
/nfs/home/nishii/streamgraph/igimv/proto3/gimv/data/result_de_e-5/result-050-4
など

2011年4月11日月曜日

StreamGraph(Incremental GIM-V) 現状と今後の方向性

Incremental GIM-V(以下、IGIMV)の現状としては、一応SPADE+UDOPで実装したものがあるが、これには以前の記事(Incremental GIM-V デバッグ中)に記したとおり、オペレータ(プロセス?)のタプルバッファによりデッドロックに似た現象が生じ、ある程度以上の数の辺を含むグラフを正常に処理できないという問題がある。
これを解決するために、作業オペレータを二種類に分割するよう実装する予定である。

実装から離れて、IGIMVの研究的な意味での貢献を考えてみる必要もある。現状では、Incremental PageRank(以下、IPR)の手法をPEGASUSのグラフ計算モデル(GIM-V)に当てはめようとはしているが、これが本当に効果的であるかは自明でない。PageRankへの有用性は、当然IPRの論文で触れられているが、それ以外についてはどうなるのか。
このあたりをはっきりとしないと、研究としての貢献が主張できない。

あまり計算モデルの一般化ということを考えずに、PageRank「など」のグラフ構造解析をストリーム的に効率的に行う、という方向で研究を進めるのはどうか、と考えている。

まず、元々のIPRは、データストリーム処理のための手法ではなく、バッチ処理を効率的に行うためのものであり、IPRはActual PageRank(全体を解析する手法)と同様の、「正しい」解析結果を得られる手法である。
ストリーム的には、このIPRのように完全な解析を行うのではなく、計算の範囲を構造変化から近い頂点(距離2,3程度?適切な距離はその頂点のページランクにも依存?)に限定して行い、完全な解析はバッチ処理(IPR)に任せる、などというのはどうだろうか。

ストリーム的に行うために、オンメモリ性を考える必要もある。頂点や辺のデータはファイルシステム上に保存しておき、計算に必要のないデータはメモリにロードしないようにする。

======

いずれにせよ、FIT(4/21〆切)までに貢献のある論文の形まで持っていくことは難しいような気がする……。
頑張って書こう!
Incremental GIM-V は、グラフ処理としても制限がきつく、データストリーム処理としてもまだ高速化(簡略化)の余地のある手法だけど、プロトタイプとしての提案である、という方向性で書く。

2011年4月8日金曜日

Incremental GIM-V は本当に有用なのか

Incremental PageRankが有用な手法であるのは、ウェブグラフの構造が、一部が変化してもそこから波及する範囲が狭いからである。
The key observation is that evolution of the Web graph is slow, with large parts of it remaining unchanged.
(Incremental Page Rank Computation on Evolving Graphs)

Incremental MethodをGIM-Vに一般化した場合に、それで適応できるアルゴリズムの実データが、実際にこのような性質を持っていない限り、大した効果がないのではないか。

論文にすることを考えるならば、Adaptive PageRank, Incremental PageRankなど、なぜ提案手法が有用であるのかセクションで述べているので、Incremental GIM-Vの場合でも、この手法を一般化しても有用であることを示す必要があるように思える。
それができないと、論文としての貢献が主張できない。
(PageRankだけ評価しても、それではIncremental PageRankの貢献およびPEGASUSの貢献を超えることができない)

2011年4月1日金曜日

Incremental GIM-V デバッグ中

igimv/proto3

submit_stream, ctcp_trigger.pyを実行
⇒ WorkerのprocessInput1 (stage==1) で、最初のmessageWW実行の後、処理が止まっている?

(追記)
PE の fusion を分けたらうまく動きそう。

(追記2)
4頂点5辺からなるグラフで、ページランクの計算に成功。

TODO:
・Managerの出力をみると、どこかでエラーが生じているらしい?要確認
・インクリメンタルに動作するかチェックする

(追記3 : 20110404 Mon.)
>Managerの出力をみると、どこかでエラーが生じているらしい?要確認
switch 文で break の書き忘れ。ログが冗長になるだけだったので、大した影響はなかった。
>インクリメンタルに動作するかチェックする
できた。

TODO:
・大きなグラフで実験(人工データ?作り方は、恣意的なものでよい?)
・igimv.dps をもとに gimv.dps を作成。動作比較

(追記4 : 20110404 Mon.)
頂点数10K, 辺数 448Kのグラフを、ワーカーノード4台で実行したところ、処理ができなかった。

理由を推測してみると、UDOPからUDOPに送るタプルが多すぎて、バッファが「デッドロック」のような状態に陥っているものだと思われる。

各Worker UDOPは同時に処理を開始し、一度の処理ブロックで最大で辺の数と同数のタプルを送る。
このとき、UDOPが送り先のオペレータの入力バッファが一杯になると、これ以上タプルを送れないので、バッファに空きができるまで待とうとする。
しかし、タプルを受け取ったオペレータはバッファの処理を行うことはない。
なぜならば、受け取った側のオペレータもまた、他のオペレータにタプルを送ろうとしている段階だからである。

===
MapReduceでは、MapとReduceが別スレッドで実行されている。
現状のigimv.dpsでは、Mapに相当する部分も、Reduceに相当する部分も、一つのUDOPにまとめてしまっているので、分けてしまうことで解決できるかも。

2011年3月4日金曜日

Incremental GIM-V でHADI(直径推定)を扱うべきか

⇒ 扱いたくない

直径推定をインクリメンタルに解く状況というのがあまり想定できない。

また、HADI では計算の反復回数が求める直径の値となるため、
インクリメンタルメソッドでも通常メソッドと同じ回数の反復を実行する必要がある。
計算の簡略化をもたらすためのインクリメンタルメソッドであるにもかかわらず、これではあまり効果がないように思える。

(本音を言うと、combine2履歴を実装するのが疲れる割にあまりメリットがないので、実装したくない)

2011年2月28日月曜日

Incremental PageRank , スケールの話

(20110301 Tue. 追記)
ページランクを正しく求める方法では、反復計算の初期値によらずただ一つのページランク(固有ベクトル)に収束するのだから、「頂点の削除」を扱わないのならば、
・元々あった頂点 ⇒ 値を変更しない
・新たに追加された頂点 ⇒ 初期値0 (id=0の頂点のみ初期値1)
で計算すれば、べき乗法で、ページランクの総和が1になるやり方でも、正しくページランクが求まるはず。

ただし、総和が1になるやり方では、ランダムジャンプの遷移によるページランクの値が
(1-c)/n となり、このnの値が変わるので、計算が収束した頂点も結局計算しなおす必要が生じるかもしれない。

そもそも、どこにもリンクしていないページの存在を正しく扱うと、そのページからは必ずランダムジャンプを行うように扱う必要が生じるため、
そのような頂点が発生すると、計算が収束した頂点のページランクにも影響が生じるので結局計算しなおす必要があるのかも?
(どこにもリンクしていない頂点が少ない(and,or)ページランクが小さい場合であれば、それによるページランクへの影響は多くの場合スレッショルド未満かもしれないが)

収束判定 (総和が1の場合) : abs(PR_new-PR_old)/PR_old < threashold (where threashold = 0.001)
Adaptive PageRankでのやり方

(20110228 Mon.)

Incremental PageRankについて、前回の全体ミーティングで、前のスライドのスケールのやり方では各ページのページランクの総和を取っても 1 にならない、と雁瀬君から指摘を受けましたが、その後、雁瀬君との議論により、総和が 1 になるようなスケールの仕方(というか、直接的にはスケールしなくて良い方法)を見つけました。

まず、本来のページランクでは総和が 1 になるようになっていますが、ここでは総和が n (頂点数) となるように全体を拡大します。
 ΣVi = n
また、グラフの構造の変化として、辺の追加と削除、頂点の追加のみを扱い、「頂点の削除」は扱わないものとします。

Incremental PageRankの計算で扱う頂点は以下の三種類に分けられます。
(計算時の分け方 Vul, Vb, Vur, Vcr とは異なる)
(1) 元からあった頂点で、スケールのみでよい (Vul, Vb)
(2) 元からあった頂点で、再計算が必要
(3) 追加された頂点で、再計算が必要

このうち、(1)と(2)はすでにページランクが割り当てられていて、その総和は(1)と(2)の頂点数と一致します。

頂点が追加されたので、その数だけ全体のページランクの総和も増える必要があります。そこで、(3)の頂点の初期ページランクとして1 を設定します。

ここで、(1)(2)(3)に対してページランク計算を実行すれば、その総和は『どこにもリンクしていない頂点は存在しない』という仮定の下であれば、頂点数と一致します。

このうち、(1)の部分はページランク計算の際に値が変わらない(はずな)ので、ページランク計算の際には(2)(3)にページランク遷移を送るだけでよい(Vb)ので、処理を簡略化できます。

本来必要だったスケール処理部分は、PageRankの値を常に「頂点数」倍にした値で計算することによって省略されます。

なお、このページランクの計算方法では、全体が強連結であるとは限らないという仮定の下で計算しているので、計算の初期値によって収束する値が異なる可能性があります。

2011年2月8日火曜日

Incremental GIM-V 必要メモリ概算

頂点id の型を Long (int64_t) とする。
頂点id を0以上の整数として扱うならば、扱うことのできる頂点数の上限は
2^64 ≒ 9.22 エクサ個となる。
SPADEの整数型に Unsigned なものってないんですかね。

===

SPADEのリファレンスをよく見てみると、"each list is limited to 2^32 - 1 entries"
とある。RWRとHADIでは頂点の値の型およびcombine2の値の型にリストを使うので、
頂点数の上限は 2^32 - 1 ≒ 4.29 ギガ個となる。

===

各アルゴリズムで必要とするメモリの大きさを概算してみる。
頂点数を N 辺数を E と置く。

PageRankの場合、

辺の値の型は Double (8 Bytes)、これに始点id (Long ;8 Bytes) 終点id (Long)
を足すので一辺あたり 24 Bytes。辺全体で 24*E Bytes。
頂点の値の型は Double。頂点全体で 8*N Bytes。
combine2の最終値を保存しておく必要がある。
combine2の値の型は Double、これに辺の終点id(Long)を足して、辺全体で 16*E Bytes。
各頂点のグラフ分割(Byte)も保存する。頂点全体で N Bytes。
あとは頂点数や辺数に依存しないデータのみなので省略。

合計すると 32*E + 9*N Bytes

頂点数が 1Mi 辺数が 100Mi とすると全体で 3209 MiB。

===

RWRの場合、

辺の値の型 : Double
辺全体 : 24*E Bytes
頂点の値の型 : DoubleList (要素数N)
頂点全体 : 24*N*N Bytes
combine2の値の型 : DoubleList (要素数N)
combine2最終値全体 : (8*N + 8)*E Bytes
グラフ分割情報全体 : N Bytes

合計 : 8*N*E + 24*N*N + 32*E + N Bytes

頂点数が 1Mi 辺数が 100Mi とすると全体で 824 TiB (+ 3201 MiB)。大きすぎ。

===

TODO:HADI, HCCについて書く。
HADIはByteListの履歴が必要となる。非常に大きくなると思う。

2011年2月7日月曜日

StreamGraph テクニカルチャレンジ(およびスライド修正点)

■ テクニカルチャレンジ
>GPU

>頂点配置の最適化
ハッシュ ⇒ マイグレーション 頂点の配置についてどこが管理するか
非対称構成などで特定のノードが遅くなる場合などにも配置最適化は有効

>フォールトトレラント
現状、GAが1つでも落ちると処理が次のステップに移れなくなりシステムが止まってしまう

>解析開始の最適タイミング
どのくらい構造変化が生じたら解析を始めるべきか

■スライド修正点
>システム全体が頂点数を知らないといけない
PageRank → スケールに必要
RWR, HADI → 頂点値とcombine2の次元数の決定に必要
解析開始トリガを通じて、グラフの総頂点数をシステムに通知する、など

>HADIについて、履歴がまだ残っている(収束していない)場合に解析が終わってしまう可能性がある
履歴が収束するまではGIM-V反復計算を行うようにする

>名称変更 : add_or_remove ⇒ update_or_remove
値もString("add", "remove")からint(1,0)などに変更

>状態遷移図で「前処理」と「GIM-V計算」の部分の色を分けてわかりやすくする

>表記変更 : 「計算内容」 ⇒ 「グラフ分割」
Q : 構造変化 | b : 変化なし、ボーダー | u : 変化なし

■とりあえず
>プロトタイプ実装しよう

2011年1月17日月曜日

個別ミーティング 2011.01.17 Mon.

・スライドにまとめる
・アルゴリズム確認、実装法について言及 : RWR, HCC, (HADI, PageRank)
・Incremental GIM-V インターフェース修正
(combine2_unchanged() を削除)
(combine2の履歴と最終結果だけのどちらを残すか選ばせるスイッチに)
・ストーリー
ストリームでインクリメンタルなグラフ処理がしたい
→ GIM-Vというグラフ処理のためのフレームがある
→ それをストリーム向けに拡張 ⇒ Incremental GIM-V
・SPADE実装に向けて、データフロー図を考えてみる (UDOPなど)

====

いろいろ他にやることもあるけど、スライドにまとめるところまでは今月中にやってしまいたい

2011年1月12日水曜日

続き : GIM-V PageRankへのIncremental PageRankの応用

前回の続き

======


HADI(直径推定アルゴリズム)への応用を考える。
グラフ構造変更前に求めた直径の値を(d_old)と置く。
グラフ構造変更後、GQ(前回を参照)に対してHADIを実行し、求まった直径の値を(d_part)と置く。

直径の値は max(d_old, d_part) となる。

ここでは、PageRankと異なり、combineAll()の計算対象に他の値を与える必要はない。
(あるいは、combineAllはビット論理和を求める演算なので、値として 0 を与える)

直径推定の場合、メッセージとして送られる値のデータ量が非常に大きくなるので
(グラフの頂点数を N(V) とおくと、1つのメッセージの値には N(V) ビット以上必要)
Incremental GIM-Vによる差分更新であれば、計算対象となるグラフが小さくて済むためネットワークコストも下がることになる。


======

PageRank, RWR, HADI まで応用できそう。
オリジナルのGIM-Vでは combine2(), combineAll(), assign(), および反復の終了条件などをアルゴリズム毎に定義する必要がある。
Incremental GIM-Vではそれに加えて、変化しない点に対する処理として、
スケール処理を行う scale_unchanged(), 変化する点のcombineAll の計算対象として加える値を決める combine2_unchanged() をアルゴリズム毎に定義させる。
(というようなアルゴリズムインターフェースにしたい)

======

スライド : Incremental GIM-V_memo_20110112.pptx
TODO: 非GIM-V なアルゴリズムにはIncremental PageRankの考え方は使えるか?(クラスタリングなど)

2011年1月7日金曜日

GIM-V PageRankへのIncremental PageRankの応用

GIM-V PageRankへのIncremental PageRankの応用を考える。
3節のStep3までは同じようにやればよい。
Step4を実行することを考える。
Vbに含まれる頂点のPageRankはこの時点で定まっていて、変更の必要はない。

VQ : 構造変化が生じた頂点、およびそこからたどれる頂点の集合

VQと、VQ内を結ぶ辺(EQ)からなるグラフ(GQ)に対してGIM-V PageRank(+拡張)を実行する。(論文中のEQ,GQの定義とは異なる点に注意)

GIM-V PageRankの手法では、ページ遷移を表わす重みをcombine2()で計算、その重みの合計からPageRankの計算をcombineAll()で行う。

combine2()は、GQ内の値からしか計算されない。しかし、VQ内の頂点のPageRankの計算はcombine2()の結果だけでなく、Vbからの重みも加味して行う必要がある。そこで、GIM-V PageRankに拡張を施す。すなわち、combine2()の結果に加えて、Vbからの重みもcombineAll()の計算対象にするように拡張すればよい。

======

Incremental PageRankの手法をGIM-V PageRankに応用する手法はわかったが、GIM-V一般には応用できるだろうか。GIM-Vによる他のアルゴリズムをまだちゃんと理解していないので、それも調べる必要がある。RWRには適用できそう。

Incremental PageRankの手法は、PageRankの計算構造に着目した最適化によるものなので、グラフ処理一般にそのまま応用できるだろうか。

======

Incremental PageRank
グラフ構造が変化(※1)したときに、
・PageRankが変化せず(※2)、他の頂点にも影響を及ぼさない頂点
・PageRankは変化しないが、他の頂点のPageRankの計算に必要な頂点
・PageRankが変化する点(構造が変化した点、変化の影響を受ける点)
に分けて計算を行う。

(※1)グラフ構造の変化として、PageRankの場合、(頂点追加、頂点削除、辺追加、辺削除)の4通りが考えられる。辺の追加と削除の場合、その辺で繋がる頂点の2つともを「構造が変化した点」として扱う。(はず。論文中では明記されていない…と思う。)

(※2)実際には、頂点数の変化に伴いPageRankの値に係数をかけるという、簡単な再計算を行う必要はある。

2010年12月22日水曜日

StreamGraph 研究の方向性とか

グラフ関連の研究ということで、2つのビジョンがある。
  1. 既存のバッチ型グラフ処理システム(ex. PEGASUS(GIM-V))のGPU高速化
  2. Framework for incremental graph processing
前者について
  • PageRank, RWRなどのGPU実装に関する研究は既にある
  • GIM-Vはそんなに汎用的な計算モデルでもない
  • ⇒GIM-VをGPU実装しても、既存研究に対してあまり差別化できない?
のであまり研究テーマとして魅力を感じない。

後者の方を見ると
  • incrementalなPageRank計算アルゴリズムが存在
  • ⇒各マイニングアプリケーションに特有のインクリメンタルな計算モデルはある
  • 汎用的なインクリメンタルなグラフ処理の計算モデルを提唱したい

インクリメンタルグラフ処理システムの研究を行うために
  • インクリメンタルGIM-V (or other) を実装
  • その上でPageRankアルゴリズムを実装
  • バッチ処理とのgapを調べる
===
まとめ:やりたいこと
  • インクリメンタルなグラフ処理の計算モデルの提唱
まずはじめに
  • incrementalなPageRank計算アルゴリズムについて理解
  • incremental GIM-V (or other) on System S (or Hadoop, or StreamScale) の実装

2010年12月8日水曜日

メモ

並列分散環境下におけるデータストリームグラフ処理に対して、ネットワークインテンシブなアプリケーションのための、ネットワークコストを削減するデータ(タスク)配置手法を考える

……その前に、
・バッチグラフ処理での配置手法に関する研究を調べる
・バッチ処理一般(MapReduceなど)における配置手法に関する研究を調べる

===================================
そもそも研究がどういう方向性に行くのかまだ決まっていない……アイディアがどこからともなくふってくるわけでもないので、いろいろ調べてみるしかないのかも

2010年11月29日月曜日

個別ミーティング 2010.11.29 Mon.

StreamGraph
・PEGASUSの動作モデルの理解(実行を通じて)⇒pptにまとめる
・Spade上でMapReduce的な反復処理の実装(案)
⇒これだけだとあまりストリーム的な要素がない
・ストリーム的な要素のアイデアを考える

ストリーム的な要素で簡単なものとしては、反復計算の途中に割り込んで
トポロジーの変化をする(頂点、辺の追加、削除)などが考えられる

2010年11月24日水曜日

メモ : StreamGraph 思考メモ

大規模グラフ処理におけるデータ分散手法
・各タスクが必要とするデータは、どのノードが保持しているか
・(ローカルデータだけで処理できるのか)
・バッチ処理、データストリーム処理を問わず
・既存手法
・・Pregel →
・・・各タスクの分散 : Hash(id) mod N
・・・メッセージパッシング、ローカルデータのみ
・・PEGASUS →
・・・Mapタスク、Reduceタスクの分散はHadoop依存
・・・データはOutput関数で渡し、Map、Reduce関数の引数で受け取る
・・・各タスクが必要とするデータはローカルデータのみ(HDFSは使わない)

GIM-V の SystemS 上実装
・研究の方針としては、数多くあるグラフアルゴリズムに対する汎用性はそんなに考えなくてよい?
・(GIM-V のように特定のアルゴリズムだけ解ければよい?)
・GIM-V のナイーブ実装、高速実装をまず理解する必要がある
・SystemS の UDOP のフィードバックループで実装できる?
・オリジナルの GIM-V は(多分)ユーザ操作による辺、頂点の追加、削除を考慮していない?(そういう機能を持たない)

GIM-V BASE implementation (IV. A)
・行列のうち値を指定していない(空)箇所はcombine2の計算がされない
・→疎行列でもそれなりに効率が良い(多分)

==============================

GIM-V拡張で辺の追加、削除を実装するのは、行列Mの値を更新すればいいだけなので多分簡単。問題は頂点の追加、削除で、行列M、ベクトルVの大きさが変化することになるので困難。

==============================
(2010.11.30 Tue.)
GIM-Vの反復の終了
PageRankを例にする。(src\pegasus\pagerank\PagerankNaive.java)
反復処理を行っているのが383~404行。
終了条件は、
1. ベクトルの値の変化がなくなったとき
2. 規定回数反復を行ったとき

1については、PageRankの値がスレッショルド(converge_threshold==0.000001)以上の変化が生じなくなった時を指す。(186~190行)
2については、デフォルトの規定回数は32回(niteration==32)となっている。

==============================
(2010.12.01 Wed.)
バッチ処理におけるデータ量爆発と、データストリーム処理におけるそれとの違いが判らない……

==============================
(2010.12.03 Fri.)
ストリーム処理向けグラフ処理のアプリケーション
http://suzumura-lab.blogspot.com/2010/11/streamgraph.html

膨大(かつstatic)なWebグラフに対するPageRankの計算を計算しているところで最も有名なのはGoogleだと思うが、そのGoogleでもPageRankの更新を行うのは2~4ヶ月に一度程度。こういった用途であればバッチ処理的に行うのが適切だろう。

ストリーム的なPageRankの計算となると、ミニブログやブログ、SNSなど話題の生起が頻繁(数日レベルのものから数時間レベルのものまで)なものが対象だろうか。
対象(頂点)は、ユーザレベルか、投稿レベルか。
辺は?

2010年11月17日水曜日

TODO list 20101117 Wed. (StreamGraph)

  • PEGASUS, Pregel の動作原理を理解
  • それぞれの計算モデルの応用性を把握(何に向いているか、いないか)
  • ストリーム処理に向いているか否か考察
  • System SなどDSMS上で実装するにはどうすればいいか考察
===
GIM-V(PEGASUS)計算モデルの高速実装は論文をちゃんと読んでちゃんと実装しないといけないので、時間がかかるかも
ナイーブ実装ならばそんなに難しくない?
===
PEGASUSの分散手法を理解する前に、MapReduce(Hadoop)の分散手法(Mapタスク、Reduceタスク、データ)を理解する必要がありそう?

2010年11月15日月曜日

メモ : Efficient PageRank on GPU Clusters

http://www.ipsj.or.jp/09sig/kaikoku/2010/ARC184HPC128.html
===
(22)Efficient PageRank on GPU Clusters
   ○Cevahir Ali(東工大),Aykanat Cevdet,Turk Ata(Bilkent大),
   Cambazoglu B. Barla(Yahoo! Research),Nukada Akira,Matsuoka Satoshi(東工大)
===
GPGPUを使ったグラフ処理の研究自体は当然既にある

PEGASUSの各アルゴリズム

Degree, PageRank, RWR など各種アルゴリズムがデフォルトで実装されている
デモの実行方法やスクリプトの場所などはマニュアルpdfを参照

例 : Degree
実行スクリプト : run_dd.sh
デモスクリプト : do_dd_catstar.sh
Javaプログラム : src/pegasus/degdist/DegDist.java

マニュアルpdfにはアルゴリズムの実装の詳細などは載っていないので、詳しく知りたければ元論文を読むなりすること

---

グラフの記述方法
頂点は番号(o-origin)で識別される
(Pregelのように文字列形式の識別子を持つわけではない)
辺は、ソース頂点番号、デスト頂点番号の対で表す

具体例を見ればわかると思う(catepillar_star.edge)

---

PEGASUSは、Hadoopを利用したグラフアルゴリズム処理システム。
MapReduce計算モデル上でグラフアルゴリズムを処理する。
アルゴリズムの「いくつかは」、GIM-Vというモデルに基づいて実行される。
(すべてのアルゴリズムがGIM-Vを用いているわけではない)

……GIM-Vを利用しているのはアルゴリズム実装であって、PEGASUSのフレームワークレベルが利用しているわけではない