メモ帳

メモ帳です.

Fast and Exact Top-k Algorithm for PageRank [AAAI'13]

PageRankにおいて高速かつ正確にTop-kを求める

読んだ論文を忘れないうちにまとめておく.
この論文は,PageRankのTop-k検索を求める手法 F-Rank を提案した.

問題

Given: Arbitrary graph G and required number of answer nodes k.
Find: Top-k nodes with respect to thier PageRank scores exactly and efficiently.

提案手法

イデア

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

  • ノードの最終的なスコアの上限値,下限値を推定.

  • 推定値に基づいて不必要なノードを枝刈りし,部分グラフを構築.

結果として,計算対象とするグラフのサイズが小さくなり,計算コストが削減される.

詳細

  • 各ステップにおいて,推定値はO(1)でincrementallyに計算可能.
  • 上限値,下限値は本来のスコアに収束する.
  • k-th highest lower bound estimation を εk とすると,upper bound estimationが εk よりも小さいノードは解になり得ない.
  • 解になり得るノードの集合を CCにreachableなノード集合をRとする.スコア計算はR全体に,推定値の計算はCを対象に行う.

実験

P2P,Web,Wikipediaの3種のデータセットを用いる.

実行時間

  • オリジナルのPageRank計算と比較して,それぞれ40%,70%,90%削減された.

正確性

  • オリジナルのPageRankで得られた結果と一致する.

以上より,高速かつ正確な結果が得られることが示された.