The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs
-
Panos Parchas, Francesco Gullo, Dimitris Papadias Francesco Bonchi
-
SIGMOD 2014
概要
-
Uncertain graphsを扱うのは大変
-
サンプリングは標本数が多くなる
-
問題:最短経路長,パターンマイニング,部分グラフ探索
-
問題毎にアドホックに開発されている→既存の枠組みが無駄→辛い
-
あるグラフで代表させたい
-
元の性質を保ったまま,決定的な代表的グラフを作るよ
-
平均次数リワイヤ(ADR)
-
近似b-マッチング(ABM)
-
最短経路長,クラスタ係数,媒介中心性等が(期待値の意味で)保存される!
問題定義
-
各頂点の平均次数の食い違いを考える
-
$$ \Delta(G;\mathcal{G}) = \sum_{v} |d_G(v) - \mathbf{E}[d_\mathcal{G}(v)]| $$
-
代表的実体: Δを最小化するG
-
IPで書いてみる
-
$$ \mathrm{min} |\mathbf{A}(\mathbf{x}-\mathbf{p})| $$
-
$$ \mathbf{x} \in {0,1}^m $$
-
Aは接続行列,pは各辺の確率
-
最近ベクトル問題の特殊ケース
ベースライン
-
最確(MP)
-
$$ p_e \geq 0.5 $$: 残す
-
$$ p_e < 0.5 $$: 消す
-
貪欲確率(GP)
-
辺を確率でソート
-
食い違いが下がる辺を順に入れていく
-
これもそんなに良くない(図とかで説明)
平均次数リワイヤ(ADR)
-
$$ \lfloor \mathbf{P} \rceil $$辺を無作為標本
-
食い違いが減るような,E'の辺とE-E'の辺を交換
近似b-マッチング(ABM)
簡単な場合
-
もし,全頂点の期待次数が整数なら,最大b-マッチングを考えれば良い
提案手法
-
フェーズ1: 極大b-マッチング
-
平均次数を最近整数に丸めた値を容量とするb-マッチングを計算
-
適当な順番で貪欲に辺を追加
-
フェーズ2: 頂点分割二部マッチング
-
構築したグラフ上で,
-
A←{食い違い≤-0.5}の頂点
-
B←{-0.5<食い違い<0}の頂点
-
C←{食い違い≥0}の頂点
-
Aを含む辺を足すと,そこの食い違いが下がる
-
いくつかの補題「B同士の辺・Cを含む辺を加えても意味ない」
-
A×Bの辺について,入れると減少する食い違いを重みとして,
-
二部グラフA∪Bでの重み付き二部マッチングを求める
実験
-
クラスタ係数とかの平均値厳密計算は無理なので,1000標本の平均
食い違いの観点から
-
MP, GP, ADR, ABMの順で悪い
-
次数: 次数分布をプロット
-
クラスタ係数: 次数-クラスタ係数をプロット
-
最短経路長: 頂点対の分布をプロット
-
媒介中心性: 次数-媒介中心性をプロット
-
一概に良いとは言えないと思う…
-
数値的に見てみたい…
-
平均の確率を変えても見てたりしてる
まとめ
-
ここがすごいなあという感じが無かった
-
もっと楽しい感じの問題かと思った
-
平均次数の食い違いは地味
-
手法も既存の組み合わせとかヒューリスティクスだからなあ
-
影響最大化でこういうのを考えるとしたら?
SIGMOD uncertain graphs
2016/01/30
最終更新:2016年01月30日 18:15