Fast and Exact Top-k Algorithm for PageRank - todo314 @ ウィキ

Fast and Exact Top-k Algorithm for PageRank

• Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Takeshi Mishima, Makoto Onizuka
• AAAI 2013

概要

• Global PageRankのtop-k頂点計算アルゴリズム
• 上下限推定＋部分グラフ構築
• 後者が新しい？

提案手法

• $$ |V|^{-1}\mathbf{1} $$から始まる普通のpower methodを回しているとする
• 下限：i反復目
• 上限：i反復目の下限＋少し（タイトっぽい感じの差）
  • 双方は極限でPageRankに一致、逐次的に更新可能
• 部分グラフ構築
  • C_i=「i-1反復目で、頂点uの上限≧top-k(n個の下限)」な頂点uだけが可能性有
  • この頂点は反復を回すとC_iはどんどん減っていく
  • C_iに到達可能な頂点集合からなる誘導部分グラフだけで考えれば良い（power iterationを考えればあたり前田のクラッカー）

実験

• 最大で数百万辺
• まぁまぁ速い

まとめ

• AAAIだと流石にアルゴリズムの実際的な挙動が分からない…

AAAI PageRank

2017/04/24