PageRank on an Evolving Graph
-
Bahman Bahmani, Ravi Kumar, Mohammad Mahdian, Eli Upfal
-
In KDD 2012
概要
-
PageRankの入力データが固定なんて意味ないだろいい加減にしろ!!
-
ちょこちょこグラフが変化するモデルを考えたよ
-
でも、実際にはあまりprobeできないので、1頂点だけout-edgeを調べる問題を考えたよ
-
頂点を選ぶ簡単なアルゴリズムを作ったけど、理論的保証があるし、実験的にも上手くいったよ
モデル
-
G^t: 時刻tでのモデル
-
G^{t+1}とG^tの違いは(極端には)多くないとする
-
高々1頂点だけprobeできる
-
どの段階でもある程度精度の良いPageRankベクトルが出るようにグラフを持っておく
-
NOTE:
-
時間計算量、空間計算量は全く気にしない
-
どうprobeすれば良いか、だけを議論している
アルゴリズム
-
Random Probing
-
Round-Robin Probing
-
Proportional Probing
-
Priority Probing
-
priorityを設定する
-
選ばれた頂点のpriorityを0に
-
それ以外はPageRankだけ上げる
実験
データセット
評価基準
-
$$ L_{\infty}(\pi^t, \phi^t) = \max_{v}|\pi^t(v)-\phi^t(u)| $$
-
$$ L_1(\pi^t, \phi^t) = \sum_{v}|\pi^t(v)-\phi^t(u)| $$
アルゴリズムの比較
一度にprobleする頂点の数
ハイブリッド
-
Round-Robin と Proportional Probingを混ぜた
-
Round-Robin多めの時に最も精度がよくなった
理論解析
まとめ
-
そういえば relative errorは使わないのかなあ…
-
アルゴリズムの中では良くても、実は50%ずれてたあとかだとやばお
-
PageRankだからいいのかな?
KDD PageRank dynamic graphs
2013-10-30 00:52:37 (Wed)
最終更新:2013年10月30日 00:52