Resampling-based Predictive Simulation for Identifying Influential Nodes ... - todo314 @ ウィキ

Resampling-based Predictive Simulation for Identifying Influential Nodes over Social Network

• 社会ネットワーク上の強影響度ノード同定のためのリサンプリングに基づく予測シミュレーション法の提案
• Kouzou Ohara, Kazumi Saito, Masahiro Kimura, Hiroshi Motoda
• JSAI 2014

概要

• ICモデルのシミュレーションは何回やればいいの？
• 真の影響度との誤差を知りたいけれど，真値が分からない

leave-N-out 交差検証

• |S|回シミュレートした
• $$ \bar{A}_S(v) $$: 試行集合Sに対するvの影響度の平均値
• パラメータNについて↓で近似誤差
• $$ \sqrt{ \langle (\bar{A}_S(v) - \bar{A}_{S \setminus B}(v))^2 \rangle_{B \in {\cal B}} } $$
• $$ {\cal B} \subset 2^S $$ は$$ \forall B \in {\cal B}, |B|=N $$を満たす
• 誤差を書き換えると
• $$ C_S(N)\bar{\sigma_S(v)} $$
  • C_S(N)は何か関数
  • $$\bar{\sigma_S(v)}$$は経験的な標準偏差

実験

• |S|=1000
• N=1, |S|/2
  • N=|S|/2の時やばそうだけど…，全パターン試さないでいいのかな…？
• 平均絶対誤差と自乗平均平方根誤差
• |S|/2は割りと真の近似誤差をうまく近似しているっぽい
  • 真の近似誤差の上限になっているとうれしい

JSAI 影響最大化 情報拡散

2014-05-25 23:04:54 (Sun)