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 よりも小さいノードは解になり得ない.
- 解になり得るノードの集合を C,Cにreachableなノード集合をRとする.スコア計算はR全体に,推定値の計算はCを対象に行う.
実験
P2P,Web,Wikipediaの3種のデータセットを用いる.
実行時間
- オリジナルのPageRank計算と比較して,それぞれ40%,70%,90%削減された.
正確性
- オリジナルのPageRankで得られた結果と一致する.
以上より,高速かつ正確な結果が得られることが示された.