Reverse Top-k Search using Random Walk with Restart (VLDB'14)
- RWR
- Bookmark Coloring Algorithm (BCA)
- 受け取って少し確定して残りを配るタイプのやつ
- ハブを活用
- ハブの頂点は受け取っても配らないことにして,後でまとめて影響を計算
- 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 を試している