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
最終更新:2014年12月06日 22:37