Maximizing Influence in an Ising Network: A Mean-Field Optimal Solution

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}) $$
    • hには予算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}) $$
    • mは定常状態で一番良いものをとる
  • $$ {\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