Influence Diffusion Dynamics and Influence Maximization in Social Networks ... - todo314 @ ウィキ

Influence Diffusion Dynamics and Influence Maximization in Social Networks with Friend and Foe Relationships

• Yanhua Li, Wei Chen, Yajun Wang, Zhi-Li Zhang
• WSDM 2013

概要

• voter modelを拡張
  • 元はunsigned network
• signed networkにした
  • 味方とは同じ意見（色）
  • 敵とは違う意見（色）
• 最初の色の分布を与えた時の挙動を解析（面白い）
• このモデルでinfluence maximization
  • ある意味で簡単
  • 確率的振舞を計算するのが超大変

Voter Model on Signed Networks

普通のvoter model

• 正重みA_ijが各辺に割当
• 頂点iが（正規化した）確率A_ijでjを選ぶ
• iはjの色に変更する
• ランダムウォーク的解釈も出来る

符号付き有向グラフ

• A_ijが正: iはjを信用
• A_ijが負: iはjを信用しない
• iは確率|A_ij|でjを選ぶ
  • 信用していたらjと同じ色，していないならjと違う色に変更する
• G=(V,E,A)をG+=(V,E+,A+)とG-=(V,E-,A-)に分解
• aperiodic…あらゆる閉路長のgcdが1
  • 無向の二部グラフとか，有向の閉路3だけはダメね
• ergodic…強連結かつaperiodic
• sink component…自身以外の頂点に辺が出ていない強連結成分
• 色々ケースがあるけれど，色々試すよ

解析

1. 短期変動
   • 白黒の初期分布に対する時刻tの分布は？
2. 収束性
   • 分布は収束する？定常分布は？

短期変動

• x_0(i): 頂点iが最初に白である確率
• 命題1 $$ x_t = P^{t}x_0 + \sum_{i=0}^{t-1}P^{i}g^{-} $$
  • g^- = D^{-1}A^-1
  • g^-(i)は頂点iから出てる負辺の重み付き割合
• x_{t-1}から漸化式を書いて展開するだけ

符号付き遷移行列の収束性

• つまり，P^iの冪和がネック
• Gの構造的平衡で3ケースになる

1. Balanced digraph
   • 分割S,Tがあり，S,T内は正辺，S,Tカットは負辺
2. Anti-balanced digraph
   • 分割S,Tがあり，S,T内は負辺，S,Tカットは正辺
3. Strictly unbalanced digraph
   • balancedでもanti-balancedでも無い

• balanced かつ anti-balancedはあり得るが，aperiodicの時は両方同時には成り立たない

• 結局変動はどう収束するの？
• ergodicグラフについて，P^tは…
  1. Balanced: 定常分布っぽいのに収束
  2. Strictly unbalanced: 0に収束
  3. Anti-balanced: 定常分布ぽいのとその-1倍の間で収束

長期変動

• t→∞の時には，↑の似た感じにxを出せる
• 1/2を中心に±異なったり振動したり…

Influence Maximization

• 最初に，k頂点を白にして，残りを黒にする
• 白頂点の期待数を短期/長期的に最大化したい
• 短期瞬時影響f_t
  • 時刻tで各頂点が白である確率の総和
• 短期平均影響f'_t
  • i=0からi=tまでの短期瞬時影響の平均
• 長期影響f
  • 短期平均影響の極限
• k=0の時をground truthとしてそこからの変量を評価関数とする
  • c_t(W)=f_t(e_W)-f_t(0)
    • e_WはWのところだけ1のベクトル
  • c'_t，cも同じ
• 実は…
  • $$ c_t(W) = \sum_{i \in W}c_t(i) $$
  • それぞれの頂点の影響力の和で良い
  • 他のも同じ
• つまり？
  • 各頂点の影響力を計算してソートして，正のものを高々k個選べばおk
• 短期の場合
  • すなおに計算O(t|E|)
• 長期の場合
  • やばお
  • 色々頑張っている

実験

• 人工的に作ったグラフは全パターン頑張っている
  • 大体tに応じて増加
  • ちゃんと理論と一致することも主張している
  • 収束が速い
    • ランダムグラフだから？
• 実世界はEpinions
  • tが小さい時にピークしてあとは減少
  • non-sinkな成分がほとんどだから？らしい

まとめ

• signed networkは何か物理辺りので見た気がしたけど，
• influence maximizationするのは面白かった
• submodularで無い（もっと強い？）ので関数値さえ出れば相当扱いやすい
• 離散ステップなのがちょっと辺？遅延とかあると楽しい
• 第一著者のYanhua LiはINFOCOMとか色々通していて結構読んでみようと思った

WSDM influence maximization modeling

2014-03-15 05:51:56 (Sat)