Spheres of Influence for More Effective Viral Marketing - todo314 @ ウィキ

Spheres of Influence for More Effective Viral Marketing

• Yasir Mehmood, Francesco Bonchi, David Garcia-Soriano
• SIGMOD 2016

概要

• 確率的な挙動の典型的なカスケードが欲しい
• 期待Jaccardを最小化する頂点集合を計算する問題
  • ありうるカスケード皆に程々に近い、安定性の指標でもある
• O(1)サンプルで定数倍近似
• 貪欲に勝った！

動機づけ

• 「少数のスーパースター」よりも「多数の凡人」の方が信頼できる
• 個々の影響力は小さいけれど、クリティカルマス到達
• 最確カスケードは良くない
  • カスケードは2^n種類あるので、最大の確率はかなり小さく、代表的とは言い難い

問題定式化

• Jaccard距離 = 1-Jaccard類似度

典型カスケード問題

• $$ \rho_{\mathcal{G},s}(C) = \mathbb{E}_{G \sim \mathcal{G}}[d_J(\mathbf{R}_{\mathcal{G}}(s), C)] $$
• $$ \rho_{\mathcal{G},s}(\cdot) $$が最大となる$$ C^* $$を見つける問題
• 困難性: ρの計算は#P-hard

Jaccard Median

• 集合が沢山与えられるので、平均Jaccard距離が最小の集合を求める問題

提案手法

戦略

• 部分グラフをサンプリングしてρを近似する
• ρの引数が$$2^n$$種類あるので、サンプル数$$ = \Theta(n) $$で悲しい
• 定理2: 最適費用が小さいならサンプルサイズは結構小さくて良い
  • $$ \alpha > $$ (最適費用)ならば、$$ \ell = \log(1/\alpha)/\alpha^2 $$で$$ (1+O(\alpha)) $$-近似解を得られる

アルゴリズム

• ランダムグラフをl個サンプル
  • 本当はρ自体がn個あるので、log nがつく
• 強連結成分分解する
• 各頂点について、各グラフから到達可能な頂点集合を計算し、Jaccard Medianを近似計算する (SODA 2010)
• NOTE: ランダムグラフは生成したものを使いまわしている

影響最大化への応用

1. 「安定性」を最適期待費用で測る
2. Sは安定なら、$$ |C^*| \approx $$平均カスケードサイズ→典型カスケードサイズを最適化しよう！
3. シード数増→拡散過程はより決定的に
4. 「Sの典型カスケード」の代わりに$$ \bigcup_{v \in S} $$ (vの典型カスケード)を使う

• やること: 典型カスケードの和集合のサイズ最大化→Maximum Coverageなので、貪欲算法

実験

• データセット
  • 最大で数百万辺、辺確率は学習／人工（weighted / 0.1）
• l = 1,000: これでいいんかい？
• 典型カスケードのサイズの平均・標準偏差・最大値
  • おおよそ勘の通り
• 典型カスケードのサイズと費用の分布
  • 小さい: 全然拡がらないので、費用が小さい（安定性が高い）
  • 大きい: 絶妙に広がるので、安定性低めだが、更に大きくすると分散が下がり安定性向上
• 影響最大化
  • シミュレーション数=1,000、CELF++使用
  • 最初は貪欲が勝っているが、シード数が増えると有る所で逆転する
  • 貪欲は各シードの寄与を上手く測れない
    • 寄与がどうなるかも実際に調べる

まとめ

• 問題の動機づけや定式化を凄く上手い、サンプルサイズに関する定理も良さそう（どの位か分からんが）
• アルゴリズムは特に面白いところ無し、Jaccard Median自体が気になる
• 疑念
  • $$\textsf{InfMax_std}$$: 実装を見ないと分からないが、再標本っぽい？
  • $$\textsf{InfMax_TC}$$: 典型カスケードの構築、再利用
    • StaticGreedyとか自分のとかを考えると、再利用の方が精度が良いので、アンフェアな比較な可能性がある
    • 再実験してみたい

SIGMOD 影響最大化 情報拡散

2016/11/27