Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs - todo314 @ ウィキ

Polynomial-Time Algorithm for Finding Densest Subgraphs in Uncertain Graphs

• Zhaonian Zou
• Workshop on Mining and Learning with Graphs

概要だけ

• Uncertain graphから期待密度最大の部分グラフ抽出
• 問題1: 制約無し
  • (期待密度)=(∑各辺の確率)
  • 各辺の周辺確率が分かっていれば良い
  • ただの最密部分グラフ
    • $$ \mathcal{O}(nm\log(n^2/m)) $$時間
• 問題2: 頂点集合Rを含む
  • 別にUncertain graph特有の何かではない
  • parametric maximum flowで同じ計算時間

まとめ

• 最初は期待してたが，スーン…ってなった．

MLG uncertain graphs 最密部分グラフ

2016/10/17