Efficient Ad-hoc Search for Personalized PageRank [SIGMOD'13]

Ad-hocにPersonalized PageRankを計算

グラフはdynamicに変化するため，ad-hocに検索する手法が重要．
この論文は，前処理することなくPersonalized PageRankのtop-kを高速かつ正確に計算する．

問題

Given: Graph G, the scaling parameter c, required number of answer nodes k, and set of query nodes Q.
Find: Top-k nodes exactly where k nodes are arranged in descending order with respect to their PPR scores.

提案手法

アイデア

反復計算の各ステップにおいて，

• 最終的なスコアの上限と下限の推定値をそれぞれ計算する．

• 推定値に基づき，不必要なノードを取り除いた部分グラフを構築．

• グラフ全体ではなく，部分グラフに対してのみスコアを計算．

詳細

• k-th highest lower estimationをεkとしたとき，upper estimationがεkよりも小さいノードは解になり得ない．

• 部分グラフは，解になり得るノードと，それにi hopで到達可能なノードの集合とする．

実験

Norredame, CNR, Email, Socialの4つのデータセットを使用．

実行速度

• それぞれ90%, 75%, 85%, 65%ほど削減できた．

• ノード数が同程度の場合でも，グラフの直径によって実行速度は異なる．

正確性

• 得られる結果は，オリジナルの手法の結果と一致する．

Flexibility

• scaling parameterが小さいほど高速

推定値がより正確になるため

Case-Studies

航空データを使用したcase studyが紹介されていた．

• scaling parameterが小さいほど，locally-orientedとなった．

最初はc=0.5に設定し，locally-orientedにしたいなら値を小さくする．そうでないなら値を大きくするのが推奨されていた．