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の値に係数をかけるという、簡単な再計算を行う必要はある。