Real-time Topic-aware Influence Maximization Using Preprocessing - todo314 @ ウィキ

Real-time Topic-aware Influence Maximization Using Preprocessing

• Wei Chen, Tian Lin, Cheng Yang
• CSoNet 2015

概要

• トピックモデルで重みがクエリで高速影響最大化
• 手法1: 実は単一トピックと考えて答えてもよさ気
• 手法2: 影響拡散の増分を少し真面目に考える
• 実験の結果，マイクロ秒で返答

問題

• $$ p_i(u,v) $$: トピックiに関する辺(u,v)の確率
• クエリ$$ I=(\lambda_1, \lambda_2, \ldots, \lambda_2) $$
• 辺確率$$ p(u,v) = \sum_i \lambda_i p_i(u,v) $$で影響最大化

データ観察

• Flixster（アメリカの映画レビューサイト）
• Arnetminer
• 各アイテムのsupp(λ)を見る
  • 大体が1か2

どの位各辺のトピックが分離してるか？

• $$ \tau_i(\theta) $$: トピックiで確率>θな辺集合
• $$ \nu_i(\theta) $$: トピックiで近傍の総和>θな頂点
• $$ \Upsilon^E_{ij}(\theta), \Upsilon^V_{ij}(\theta) $$: トピックi,jの重複
• fully separable $$ \Upsilon^V_{ij}(0) = 0 $$
• 当たり前だけど，トピック毎に非連結になってる…かなり簡単
• Arnetminerでは重複が少ない…分野横断が少ない
• Flixsterでは重複が多い…割りと自然
• 観察1: 確率に関するトピック分離はネットワーク依存

シードがどの位類似しているか？

• 色んなアイテムを作っても割りと選んだシードは似てる
• 観察2: 混合トピックでのシードは単一トピックでのシードから来る

前処理

最優トピック選択(BTS)アルゴリズム

$$i$$\$$\Lambda$$	$$\lambda^c_0$$	$$\cdots$$	$$\lambda^c_m$$
1
$$\vdots$$
d

• $$0 = \lambda^c_0 < \lambda^c_1 < \cdots < \lambda^c_m = 1$$
  • クエリを量子化

アルゴリズム

• 前計算: i番目がλ^c_jなIについてシードを計算（d×m通り）

1. $$I = (\lambda_1, \ldots, \lambda_d)$$クエリが来る
2. $$I' = (\underline{\lambda}_1, \ldots, \underline{\lambda}_d)$$に量子化
3. i(1≦i≦d)番目が $$ \underline{\lambda}_i $$な奴から一番良いのを変える
   • 前計算で既に前計算してるので

• σはpについて劣加法性？
  • $$ \sigma(S, \sum_{i \in D^+_I} \lambda_i p_i) \leq c \sum_{i \in D^+_I}\sigma(S, \lambda_i p_i) $$
  • 各辺を2彩色した木だとcのboundが怪しいらしい？
  • fully separableなら1-劣加法性（非連結なので自明）
• 定理4.1
  • $$ \frac{1-1/e}{c|D^+_I|\mu_{\max}} $$近似
  • 私的直感
    • 非ゼロ1つのλで最良を選ぶから$$ |D^+_I| $$倍
    • 劣加法性の分c倍
    • $$ \mu_{\max} $$は量子化の粗さ
• 典型的なのはc=1, μmax=1.5, |D^+_I|=2
  • ほんと？

増分影響ソート(MIS)アルゴリズム

• 補題: fully separableな時について自明なことを言ってる？ アルゴリズム
• 分離しているとした時の貪欲での増分を覚えておく
• 定理: fully separableなら普通の貪欲と同じ解を返す
  • 想定している事をしてる

実験

• MISとBTS: 数マイクロ秒
• 割りと良さそう

まとめ

• 自明な時なら上手くいくアルゴリズムだなぁ
• まだ非自明に良い理論的保証を持つアルゴリズムは無いので色々やることはありそう

CSoNet 影響最大化 情報拡散

2015/10/13 1:33