Fast Incremental and Personalized PageRank - todo314 @ ウィキ

Fast Incremental and Personalized PageRank

• Bahman Bahmani, Abdur Chowdhury, Ashish Goel
• VLDB 2010

概要

• PageRankの動的更新
• ランダムウォークを大量に保持して動的更新に応じて切断して再ウォーク

提案手法

• 適当な始点でランダムウォークをR本保持
  • PageRankなら各始点を一様ランダムに選ぶ
  • PPRなら始点をPersonalizedベクトルで重み付け
• 辺ijが追加・削除されたら，iを通るウォークについて，
• 「そこから」ウォークし直す
• m辺がランダムに挿入された時の期待更新ステップ数はO(Rlog m)

欠点

• 誤差をε以下にするためにはR=O(1/ε^2)本のウォークが必要

PageRank VLDB 動的グラフ

2014/12/06