Sensitivity of Diffusion Dynamics to Network Uncertainty - todo314 @ ウィキ

Sensitivity of Diffusion Dynamics to Network Uncertainty

• Abhijin Adiga, Chris Kuhlman, Henning S. Mortveit, Anil Kumar S. Vullikanti
  • ネットワークダイナミクスとかの研究所
• AAAI 2013

概要

• IC/LTモデルについて考える
• グラフに辺をちょっと足したら、influence spreadはどうなるか？がメイン
• アクティブノード数の期待値について適当な仮定をおいて解析

モデルとか

ノイズモデル

• G=(V, E): 元のグラフ
• R(ε)=(V, E(ε))
  • (u, v)∈E(ε) wp ε/n
• G'=G ⊕ R(ε)
  • E ⊕ E(ε)を辺集合とする
• G+R(ε)
  • E∪E(ε)
  • 大体こっち？

解析

ICモデル

• random graph
  • 確率がしきい値以上/以下で、連結成分の大きさが変わる
• 定理1
  1. 仮定1: p<p_cならばG(p)の連結成分は大体o(√n)
  2. 仮定2: 連結成分の個数がほとんど(N,(1+μ)N)におさまるN=N(n, p)とμがある
  • p<p_cならε_t=N/(pn)が存在して
  1. ε<ε_tならG+R(ε)でのσはGでのσと大体同じ
  2. ε>c'ε_tならσはめっちゃでかくなる

LTモデル

• b_{v,w} = 1/deg(v)
• 定理2
  • 各頂点が確率sで選ばれるシードをとるとG+R(ε)でのσは
  • O(s(Δ(G) + ε + log n)log n)
  • sとεが小さければあんまり影響ない
  • これはσ_{G+R(ε)}-σ_Gについてってことでいいのかな？

実験

ICモデルについて

• pとsを色々変える
• εに従ってσはどう変わるかを実験的に見る
• ε_t（差が出る所）を定理からと実験から求めてみる
• 両方で出た答えは似ているっぽいぞ！

LTモデルについて

• シードの確率sを色々変える
• εに従って（ry
• 省略したよ(・ω<)

AAAI information diffusion

2013-11-16 21:29:02 (Sat)