Fast Algorithms for Top-k Personalized PageRank Queries - todo314 @ ウィキ

Fast Algorithms for Top-k Personalized PageRank Queries

• Manish Gupta, Amit Pathak, Soumen Chakrabarti
• WWW 2008

概要だけ（で十分なので）

• PPR上位k頂点を抽出したい
• 基本的にはBookmark Coloring Algorithm (BCA)
• 途中で打ち切れる
  • 初期<解, 残差>を$$ \langle \mathbf{0}, \mathbf{v} \rangle $$で始めると、
  • 推定値≦真値≦推定値+||残差||
    • 扱いやすい範囲で、もう少し改善している
• この条件を使って枝刈り
• 出力したい頂点を限定した設定も考えているけどスルー
• 4倍速くなりました

まとめ

• 2ページだし、まぁ普通

PageRank WWW personalized PageRank

2017/04/19