The Pursuit of a Good Possible World: Extracting Representative Instances of ...

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)
    • b-マッチング→最大重み二部マッチング
  • 最短経路長,クラスタ係数,媒介中心性等が(期待値の意味で)保存される!

問題定義

  • 各頂点の平均次数の食い違いを考える
  • $$ \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)

  1. $$ \lfloor \mathbf{P} \rceil $$辺を無作為標本
  2. 食い違いが減るような,E'の辺とE-E'の辺を交換
    • 局所探索,ステップ数はパラメータ

近似b-マッチング(ABM)

簡単な場合

  • もし,全頂点の期待次数が整数なら,最大b-マッチングを考えれば良い
    • $$ O(m^{3/2}) $$時間で求まる

提案手法

  • フェーズ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