Triangle-Based Representative Possible Worlds of Uncertain Graphs
-
Shaoying Song, Zhaonian Zou, Kang Liu
-
DASFAA 2016
概要
問題定義
-
$$ \sum_{v}|d_{G}(v)-\bar{d}_{\mathcal{G}}(v)| + \sum_{v}|t_{G}(v)-\bar{t}_{\mathcal{G}}(v)| $$を最小化せよ
-
t(v): vを含む△の個数/平均個数
-
各△の出現確率を足し合わせればOK
提案手法
-
初期グラフを作る
-
目的関数値を減らすように努力する
-
辺取替で良くなる場合
-
辺挿入で良くなる場合
-
それぞれ目的関数値の更新がそこそこ速い
実験
-
次数,三角形次数,クラスタ係数,最短経路長を見てみる
-
クラスタ係数がそこそこ改善
-
最短路は相変わらず微妙
まとめ
-
特に困難性も近似解析も何もないなあ
-
DASFAAはちゃんと書いたら強い貢献が弱くても通るのかな?
-
実験で,プロットして満足するの止めて欲しいなあ
DASFAA uncertain graphs
2016/05/11
最終更新:2016年05月11日 02:45