On the Approximability of Influence in Social Networks - todo314 @ ウィキ

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

SODA 影響最大化

2014-09-25 02:06:25 (Thu)