Triangle-Based Representative Possible Worlds of Uncertain Graphs - todo314 @ ウィキ

Triangle-Based Representative Possible Worlds of Uncertain Graphs

• Shaoying Song, Zhaonian Zou, Kang Liu
• DASFAA 2016

概要

• 三角形次数を保存する決定的グラフを抽出するよ！
• The Pursuit of a Good Possible World: Extracting Representative Instances of ...の発展
• やってることは簡単なヒューリスティクス

問題定義

• $$ \sum_{v}|d_{G}(v)-\bar{d}_{\mathcal{G}}(v)| + \sum_{v}|t_{G}(v)-\bar{t}_{\mathcal{G}}(v)| $$を最小化せよ
  • t(v): vを含む△の個数／平均個数
  • 各△の出現確率を足し合わせればOK

提案手法

1. 初期グラフを作る
   • 大体平均辺数まで適当にサンプリング
2. 目的関数値を減らすように努力する
   • 辺取替で良くなる場合
   • 辺挿入で良くなる場合
   • それぞれ目的関数値の更新がそこそこ速い

実験

• 次数，三角形次数，クラスタ係数，最短経路長を見てみる
• クラスタ係数がそこそこ改善
• 最短路は相変わらず微妙

まとめ

• 特に困難性も近似解析も何もないなあ
• DASFAAはちゃんと書いたら強い貢献が弱くても通るのかな？
• 実験で，プロットして満足するの止めて欲しいなあ

DASFAA uncertain graphs

2016/05/11