「On the Approximability of Influence in Social Networks」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* On the Approximability of Influence in Social Networks
- Ning Chen
- SODA 2008
- メモ程度に
* モデル
- 無向グラフG
- 閾値1≦t(v)≦deg(v)
- 近傍の内t(v)以上が活性化したら自分も活性化
- Target Set Selection 問題:
-- ある割合の頂点数を活性化するためのシードサイズを最小化したい
- ちょっと違うけどまあ
* 結果
- $$ O(2^{\log^{1-\epsilon}n}) $$で近似できない（仮定のもと）
- Majority Thresholds
-- 半分以上で活性化
- Small Thresholds
-- 小さい定数
- Unanimous Thresholds
-- 閾値=次数
-- 割と簡単
- Tree Structure
&tags()
&update()
