Spheres of Influence for More Effective Viral Marketing
-
Yasir Mehmood, Francesco Bonchi, David Garcia-Soriano
-
SIGMOD 2016
概要
-
確率的な挙動の典型的なカスケードが欲しい
-
期待Jaccardを最小化する頂点集合を計算する問題
-
ありうるカスケード皆に程々に近い、安定性の指標でもある
-
O(1)サンプルで定数倍近似
-
貪欲に勝った!
動機づけ
-
「少数のスーパースター」よりも「多数の凡人」の方が信頼できる
-
個々の影響力は小さいけれど、クリティカルマス到達
-
最確カスケードは良くない
-
カスケードは2^n種類あるので、最大の確率はかなり小さく、代表的とは言い難い
問題定式化
典型カスケード問題
-
$$ \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個サンプル
-
強連結成分分解する
-
各頂点について、各グラフから到達可能な頂点集合を計算し、Jaccard Medianを近似計算する (SODA 2010)
-
NOTE: ランダムグラフは生成したものを使いまわしている
影響最大化への応用
-
「安定性」を最適期待費用で測る
-
Sは安定なら、$$ |C^*| \approx $$平均カスケードサイズ→典型カスケードサイズを最適化しよう!
-
シード数増→拡散過程はより決定的に
-
「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
最終更新:2016年11月30日 02:30