Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution
-
Christopher W. Lynn, Daniel D. Lee
-
NIPS 2016
概要
-
Isingモデル上の影響最大化
-
意見=スピン、外部影響=外部磁場、影響力=J
-
相互作用の反復による意見の「平衡」状態
-
平均場近似で解く
-
外部磁場に対して滑らかかつ凹になる十分条件
-
平均場の安定非負定常分布の存在に関する条件
-
実験もしたよ
問題定式化
Ising influence maximization
-
$$ \Pr[\sigma_i(t+1) \mid \sigma(t)] = \frac{\exp\Bigl( \beta \sum_{j}J_{ij}\sigma_j(t) + h_i \Bigr)}{\sum_{\sigma'_i = \pm 1}\exp\Bigl( \beta \sigma'_i \sum_{j}J_{ij}\sigma_j(t) + h_i \Bigr)} $$
-
$$ M({\bf h}) = \sum_i \langle \sigma_i \rangle $$
-
$$ {\bf h}^* = \mathrm{argmax}_{{\bf h}} M({\bf h}^{(0)} + {\bf h}) $$
-
で、これを解くのはしんどい
Mean-field Ising influence maximization
-
$$ m_i = \tanh \Bigl[ \beta \Bigl( \sum_{j} J_{ij} m_j + h_i \Bigr) \Bigr] $$
-
miは<σi>の近似で、定常状態=上の解=不動点を求めたい
-
hに対する目的関数 $$ M^{MF}({\bf h}) = \max_{{\bf m}} \sum_{i} m_i({\bf h}) $$
-
$$ {\bf h}^* = \mathrm{argmax}_{{\bf h}} M^{MF}({\bf h}^{(0)}+{\bf h}) $$
性質解析
-
Jが強連結∧安定非負定常分布が唯一に存在→hについて滑らかかつ凸
-
(maxが消えて)最急降下法でOKになり、最適解が求まる
-
$${\bf h}^{(0)} \geq {\bf 0}$$→安定非負定常分布が存在
-
知見: βが高い時、
-
$$ {\bf h}^* \approx \mathrm{argmax}_{{\bf h}} \min_{i} (d_i^{in} + h_i^{(0)} + h_i) $$
-
h^{(0)}が一様なら、低入次数に振ったほうが良い
-
本当は、βcという閾値によって変わるんだけど、めんどいので省略
実験
-
βcを境にした相転移とか、解の(外部磁場の意味での)平均次数が低くなることを観測
まとめ
-
思ったよりはそれっぽい感じだった
-
Isingモデルが意見ダイナミクスとかでどんくらい使える(?)か知りたい
Isingモデル NIPS 影響最大化
2017/01/17
最終更新:2017年01月17日 19:39