・スライドにまとめる
・アルゴリズム確認、実装法について言及 : RWR, HCC, (HADI, PageRank)
・Incremental GIM-V インターフェース修正
（combine2_unchanged() を削除）
（combine2の履歴と最終結果だけのどちらを残すか選ばせるスイッチに）
・ストーリー
ストリームでインクリメンタルなグラフ処理がしたい
→ GIM-Vというグラフ処理のためのフレームがある
→ それをストリーム向けに拡張 ⇒ Incremental GIM-V
・SPADE実装に向けて、データフロー図を考えてみる (UDOPなど)
====
いろいろ他にやることもあるけど、スライドにまとめるところまでは今月中にやってしまいたい
2011年1月17日月曜日
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の考え方は使えるか？（クラスタリングなど）
======
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
オリジナルの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の値に係数をかけるという、簡単な再計算を行う必要はある。
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の値に係数をかけるという、簡単な再計算を行う必要はある。
登録:
投稿 (Atom)