Core Decomposition of Uncertain Graphs (KDD'14)

定義

• uncertain graph
  • 各辺に対し存在する確率が与えられる
  • リンク予測の出力，影響，protein-interaction （ノイズ）
• (k, η)-core
  • 極大部分グラフ H, [deg_H(v) ≧ k] ≧ η

計算

• 小さい方から剥ぎ取る
• 確率の計算がちょっと入るが簡単な DP

応用実験

• 影響最大化：密グラフとして抽出する前処理
• Task-Driven Team Formulation：それっぽいチームを探す