UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ... - todo314 @ ウィキ

UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social Networks

• Chuan Zhou, Peng Zhang, Jing Guo, Xingquan Zhu, Li Guo
• ICDM 2013

概要

• CELFは最初のiterationが遅い！
• もうちょっとだけ早くするんじゃ
• 大まかな見積もりを行列計算でやる
• タイトかは分からんが正しい上界が出る
• 上界順にMonte-Carloして、それが最上位って分かったら抜ける
• シミュレーション数95%カット
• 速度は2~5倍(´・ω・`)

提案手法

上界の見積もり方

• Pr_{S,t}[v]: Sが時刻tにvをactivateする確率
• ↑の値はvの近傍uvについて、そのどれもが失敗することは無い、で書けるので
• 1-Π_{uv}(1-Pr_{S,t-1}[u]*p_{uv})
• こんな感じ（気分）
• 1-Π(1-x_i)≦Σx_iで抑えれば
• Pr_{S,t}[v]≦Σ_u Pr_{S,t-1}[u]*p_{uv}
• ポイントは↑が厳密に上界であること（他のヒューリスティクスとは違う
• しかもシンプルな式なのでp_{uv}を要素に持つ行列のべき乗和Pで表現できる
• 正確には
• Π_{S,t}を↑のPrのベクトルと思えば
• Π_{S,t}≦Π_{S,t-1}P
• これを繰り返して
• σ(S)≦Σ_t Π_{S,0}P^t I
• まぁ結局(E-P)の逆行列になる（上の式からあきらか

UBLF

1. 最初に上ので上界を出す
2. 上界の大きい順に頂点vを取り出す
3. σ(v)を計算
4. σ(v)≧次の上界ならもうvでOK

• もっと簡単に一回だけ上界出してそれをスコアとしてk個選んでるけどダメだろう…

実験

• 比較対象
  • CELF、PageRank、Degree、Random
• Monte-Carloシミュレーション数
  • 総回数は5%位に減った
• influence spread
  • CELFと同じ
• 計算時間
• CELFの2～5倍速くなった
  • (´・ω・`)

まとめ

• 上界がまともに出てくるという点で面白いと思った
• 実際にシミュレーション回数が激減しているのもすごい
• ただ余り速くなっていないので本末転倒
• もっと早く2008,9年とかだったら高評価だったに違いない
• いずれにしてもICDM通っているのでなんだかな～という感じ

ICDM influence maximization

2014-02-16 22:59:13 (Sun)