Efficient Ad-hoc Search for Personalized PageRank - todo314 @ ウィキ

Efficient Ad-hoc Search for Personalized PageRank

• Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Takeshi Mishima, Makoto Onizuka
• SIGMOD 2013

概要

• PPRが上位k頂点を順位つきで出力
• 提案手法Castanet
• 前処理、パラメータ無し、厳密
• 既存手法より速い

提案手法

• 大まかにはFast and Exact Top-k Algorithm for PageRankと大体同じ
• 上限下限の反復改善計算
  • 細かい数式が改善している？
• 部分グラフ抽出
  • (上位kに必ず入らない)∨(順位が確定した)頂点はどうでも良い
  • 候補となりうる頂点に到達可能な頂点からなる部分グラフだけを見れば良い
  • もう少し凝った事をしているけどあまり読んでいない

実験

• 数百万辺のグラフ
• [Fujiwara-Nakatsuji-Yamamuro. KDD'12]Efficient Personalized PageRank with Accuracy Assuranceと比較→圧勝！

まとめ

• こういうタイプの手法の効率の限界は何処だろう
• 上下限だけなら億辺でやってもあまり変わらない？

PageRank SIGMOD personalized PageRank

2017/04/27