PageRank on an Evolving Graph

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
    • 現在のPageRankに比例した確率で頂点を選ぶ
  • 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)| $$

アルゴリズムの比較

  • Priority Probingが一番良い
    • 大体上の紹介順

一度にprobleする頂点の数

  • 一度に2、4個できてもそんなに変わらん

ハイブリッド

  • 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