Clustering Large Probabilistic Graphs
-
George Kollios, Michalis Potamias, Evimaria Terzi
-
TKDE 2013
概要
-
Uncertain graphのクラスタリング
-
編集距離ベースの目的関数
-
Correlation Clusteringと同じになる
-
その他自明な拡張
問題定義+提案手法
pClusterEdit
-
クラスタグラフ: (Gと同じ頂点集合を持つ、)互いに素なクリークの和集合
-
期待編集距離: 「Gからサンプルした部分グラフ」と「クラスタグラフ」の(辺の意味での)編集距離の期待値
-
辺毎に考えれば良く、クラスタグラフに辺が無い→p(e)/有る→1-p(e)
-
これはCorrelation Clusteringですね
提案手法
-
pKwikCluster
-
STOC '05の手法を適用すれば線形時間5近似算法
-
ClusterEdit問題(Discrete Applied Mathematics '04)の近似可能性を解決したと主張しているが何だかなあ…
-
Furthest…top-down
-
全体を一つのクラスタと見做す
-
遠い二頂点を選び、それらを中心とするクラスタに分割
-
十分小さくなるまで繰り返し、一番良かったものを返す
-
O(nk^2)時間
-
Agglomerative…bottom-up
p2ClusterEdit
-
クラスタグラフは決定的だった
-
(α,β)-クラスタグラフ: Pr[クリーク内の辺が存在]=α、Pr[クリーク間の辺が存在]=β
-
(α,1-α)が与えられた下で最小化
-
期待編集距離はクラスタグラフも確率的な設定で自然に考えられる
-
辺毎に考えれば良いので、結局pClusterEditに出来る
-
最適なαを決めたい: α=0/1が最適値をとる∵αについて線形だから
p3ClusterEdit
-
自明な事だけ
-
(α,β)が与えられた下で最小化
-
最適な(α,β)を決めたい: (0,0),(0,1),(1,0),(1,1)のどれかが最適値をとる
実験
まとめ
-
コレ本当にTKDEに通ったの?
-
問題定義が実際には逆で、Correlation Clusteringになるように、クラスタグラフだとか編集距離だとかを考えたのだと思う
-
全体的に自明過ぎる
-
定数近似線形時間算法があるのに、他のヒューリスティクスを提案する意味が分からない
TKDE uncertain graphs クラスタリング
2016/12/04
最終更新:2016年12月04日 01:38