Competitive Influence Maximization in Social Networks - todo314 @ ウィキ

Competitive Influence Maximization in Social Networks

• Shishir Bharathi, David Kempe, Mahyar Salek
• WINE 2007

概要

モデル

• 辺uvが試行成功したら指数分布の遅延時間T_{uv}が発生する
• bプレイヤがサイズk_i以下の集合S_iを選択する
• 複数人が選択した頂点はランダムに誰かの頂点になる
• これでカスケードをしていく
• 純粋戦略ナッシュ均衡は無い（？）
• 混合戦略ナッシュ均衡は有る

戦略

• もし，他の人の戦略が固定されていたら
• 自分の戦略に対するσは単調かつ劣モジュラ

First Mover Strategies

Influence Maximization on Bidirected Trees

• bi-directed treeならinfluence maximizationはFPTAS
• 動的計画法+確率のrounding

まとめ

• 難しい…

WINE influence maximization modeling

2014-02-24 21:03:21 (Mon)