読者です 読者をやめる 読者になる 読者になる

Core Decomposition of Uncertain Graphs (KDD'14)

定義

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

計算

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

応用実験

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