Efficient Estimation of Influence Functions for SIS Model on Social Networks - todo314 @ ウィキ

Efficient Estimation of Influence Functions for SIS Model on Social Networks

• Masahiro Kimura, Kazumi Saito, Hiroshi Motoda
• IJCAI 2009

概要

• SISモデルのシミュレートを高速化
• ボンドパーコレーションと適当な枝刈り
  • 精度には影響しない
• 実験で数百倍以上速い

SISモデル

• 時刻は離散的
• 最初に頂点を活性化
• 活性頂点は非活性な頂点を与えられた確率で活性化
  • 成功したら次の時刻に活性化
• 何も影響されなかった頂点は次の時刻に非活性化
• 求めたいもの
  • σ(v,t): 時刻0でvを活性化したとき，時刻tで活性な頂点の数の期待値

提案手法

• レイヤーグラフを作る
  • (u_{t-1}, v_t)に辺を張る
• σ(v,t)は到達可能な頂点数の平均値で近似できる
• 枝刈り
  • どうあっても影響されない頂点を無視する
  • つまり逆向きに見て時刻0のグラフの頂点にたどり着かないような頂点のこと
  • 毎時刻↑は簡単に計算できる
• 枝刈り
  • 途中から到達可能性の意味で同一視できる頂点対が発生するのでそれを同一視
  • 一度同一視された頂点対は分かれることは無い（当たり前）
• 計算量は落ちているけど，nとかTが消えるとかでは無い

実験

• 10K頂点，100K辺
• 2個目の枝刈りが以外と効果的
  • σ(v)を全部のvについて求めないといけないからかな
• ナイーブよりも数百倍以上速くなった

まとめ

• 手法が簡単だし，劇的な改善っぽくないけど通るんだなあ…

IJCAI SISモデル 情報拡散

2014-06-06 00:34:24 (Fri)