iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

Reverse Top-k Search using Random Walk with Restart (VLDB'14)

  • RWR
    • Bookmark Coloring Algorithm (BCA)
      • 受け取って少し確定して残りを配るタイプのやつ
    • ハブを活用
      • ハブの頂点は受け取っても配らないことにして,後でまとめて影響を計算
  • Reverse Top-K RWR Query
    • 頂点 q と k → 頂点 u からのの RWR で q が top-k に入る u を全て答える
    • 応用:「こいつに強い影響を与えている物の集合」が得られる
      • spam detection
      • popularity of authors in co-authorship network
      • promotion in co-purchase graph
  • Offline indexing
    • 各頂点から BCA を t ステップ走らせる → RWR の下界
    • 改良:ハブ,サイズ圧縮,・・s
  • Online Query Algorithm
    • proximity の上界と下界を狭めていくよくあるタイプ
  • 実験結果
    • web-Google で前処理時間 10^6 秒とは・・・
  • 応用実験 (5.4)
    • spam detection, co-author network を試している