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を拡張
-
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
-
ergodic…強連結かつaperiodic
-
sink component…自身以外の頂点に辺が出ていない強連結成分
-
色々ケースがあるけれど,色々試すよ
解析
-
短期変動
-
収束性
短期変動
-
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ケースになる
-
Balanced digraph
-
分割S,Tがあり,S,T内は正辺,S,Tカットは負辺
-
Anti-balanced digraph
-
分割S,Tがあり,S,T内は負辺,S,Tカットは正辺
-
Strictly unbalanced digraph
-
balancedでもanti-balancedでも無い
-
balanced かつ anti-balancedはあり得るが,aperiodicの時は両方同時には成り立たない
-
結局変動はどう収束するの?
-
ergodicグラフについて,P^tは…
-
Balanced: 定常分布っぽいのに収束
-
Strictly unbalanced: 0に収束
-
Anti-balanced: 定常分布ぽいのとその-1倍の間で収束
長期変動
-
t→∞の時には,↑の似た感じにxを出せる
-
1/2を中心に±異なったり振動したり…
Influence Maximization
-
最初に,k頂点を白にして,残りを黒にする
-
白頂点の期待数を短期/長期的に最大化したい
-
短期瞬時影響f_t
-
短期平均影響f'_t
-
長期影響f
-
k=0の時をground truthとしてそこからの変量を評価関数とする
-
c_t(W)=f_t(e_W)-f_t(0)
-
c'_t,cも同じ
-
実は…
-
$$ c_t(W) = \sum_{i \in W}c_t(i) $$
-
それぞれの頂点の影響力の和で良い
-
他のも同じ
-
つまり?
-
各頂点の影響力を計算してソートして,正のものを高々k個選べばおk
-
短期の場合
-
長期の場合
実験
-
人工的に作ったグラフは全パターン頑張っている
-
大体tに応じて増加
-
ちゃんと理論と一致することも主張している
-
収束が速い
-
実世界はEpinions
-
tが小さい時にピークしてあとは減少
-
non-sinkな成分がほとんどだから?らしい
まとめ
-
signed networkは何か物理辺りので見た気がしたけど,
-
influence maximizationするのは面白かった
-
submodularで無い(もっと強い?)ので関数値さえ出れば相当扱いやすい
-
離散ステップなのがちょっと辺?遅延とかあると楽しい
-
第一著者のYanhua LiはINFOCOMとか色々通していて結構読んでみようと思った
WSDM influence maximization modeling
2014-03-15 05:51:56 (Sat)
最終更新:2014年03月15日 05:51