続き : 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の考え方は使えるか？（クラスタリングなど）