Maximizing Social Influence in Nearly Optimal Time (SODA'13)

Quasilinear-time Algorithm

  1. ハイパーグラフの構築
    • 各ノード「に」伝搬するノード集合を計算する(転置グラフを用いる)
    • シードを1つランダムに選び逆向きシミュレート(BFS)
      • 訪れたノード集合をハイパーエッジにする
    • アクティブノードの総数がある程度大きくなったら終了
  2. シード集合の選択
    • ハイパーグラフでの次数最大を貪欲に選ぶ
    • 選んだらそいつを含んでるハイパーエッジ削除
定理と証明
  • 定理
    • 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