The Importance of Communities for Learning to Influence - todo314 @ ウィキ

The Importance of Communities for Learning to Influence

• Eric Balkanski, Nicole Immorlica, Yaron Singer
• NIPS 2017

概要

• The Power of Optimization from Samplesはcurvature制限時だった
• 今回は影響最大化をコミュニティ構造が明らかな場合、OPSの枠組みでなんとかするよ
• コミュニティの大きさを捉えられそうなアルゴリズムを提案
• SBMの簡単な設定で近似比を証明

アルゴリズム COmmunity Pruning from Samples

設定

• 無向なので、基本的に連結成分の大きさ（の和）の期待値が影響力になる
• underlyingなグラフがSBMだったりするのを考える

記述

1. 一次貢献の降順に頂点を整列
   • 一次貢献 := ランダム集合（vを含まぬ）にvを追加したときの増加量の期待値
2. 頂点aを順番に走査し、走査済みのある頂点bと重複が大きいなら、aを除く
   • 二次貢献 := "aを含まず" AND "bを含む"ランダム集合にaを足したときの増加量の期待値
   • これが一次貢献よりも相対的に小さい→bがあれば良いので、aはほぼ無意味
3. 前からk頂点を返す

解析

強い仮定

1. コミュニティ間を結ぶ辺が無い
2. SBMに従ってグラフが生成し、そこからランダムグラフ
   • つまり、コミュニティC内の辺は確率「p_C := (SBの確率)×(ICの確率)」で残る
3. p_C > 3log|C|/|C| (dense)
   • ER60から高確率でCは連結になる
4. シード集合はめちゃ小さい

• 結果: 一次貢献はほぼコミュニティの大きさ、二次貢献も良さげな結果、組み合わせると、1-o(1)近似

弱い仮定

1. コミュニティ内 p_C >= (1+ε)/|C| (tight)
   • →定数割合の巨大成分
2. コミュニティ間 p_C <= (1-ε)/|C| (loose)
   • →定数個の成分（全然選ばれない）

実験

• SBM, ER, PA, Facebook, DBLP

まとめ

• めっちゃ仮定が強いが良さそうではある
• 辺確率が定数なのは仕方ないかな…。
• 基本的にランダムサンプリングができている前提のモデルだが、もうちょっと良さげなのはないかしら？

NIPS OPS 劣モジュラ 影響最大化

2018/09/16