Maximizing Social Influence in Nearly Optimal Time (SODA'13)
Quasilinear-time Algorithm
- ハイパーグラフの構築
- 各ノード「に」伝搬するノード集合を計算する(転置グラフを用いる)
- シードを1つランダムに選び逆向きシミュレート(BFS)
- 訪れたノード集合をハイパーエッジにする
- アクティブノードの総数がある程度大きくなったら終了
- シード集合の選択
- ハイパーグラフでの次数最大を貪欲に選ぶ
- 選んだらそいつを含んでるハイパーエッジ削除
定理と証明
- 定理
- O*1 時間
- 確率 3/5 以上で近似比 (1 - (1/e) - ε)
- Observation 3.2
- 集合 S による influence 期待値 = ハイパーグラフでの S の次数
- Lemma 3.3
- ハイパーエッジの本数がある程度多くなる
- Markov 不等式
- Lemma 3.4
- Lemma 3.3 の下界が成り立っているとき,Observation 3.2 の値同士の差がある程度小さい
- Chernoff bound
- Lemma 3.6
- そういう時,greedy algorithm での解の値がどうなるか
- Union Bound
Sublinear-time Algorithm
- 十分な数の辺が得られないので確率的に適当に頂点を選ぶ
- O(b (m+n) log n) 時間,確率 3/5,近似比 min{1/4, b}
*1:m+n) log n ε^(-3