Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms - todo314 @ ウィキ

Truss Decomposition of Probabilistic Graphs: Semantics and Algorithms

• Xin Huang, Wei Lu, Laks V.S. Lakshmanan
• SIGMOD 2016

概要

• Core decomposition of uncertain graphsのk-trussへの拡張

1. 局所的：部分グラフの各辺がk-2△に含まれる確率≧γ
   • k-coreっぽく辺を取り除いていく
   • 当該確率はDPで計算
2. 大域的：部分グラフ全体がk-trussを含む≧γ
   • 確率の厳密計算が#P-hard
   • ランダムサンプリングして探索

• 実験しました

問題定式化

• 局所$$(k, \gamma)$$-truss
  • $$ \Pr[\sup_{H}(e)\geq k-2] \geq \gamma $$な部分グラフH
• 大域$$(k, \gamma)$$-truss
  • $$ \alpha_k(H, e) := $$ ($$e$$を含む$$k$$-trussが出て来る確率) $$ \geq \gamma $$
  • が全ての辺eについて成り立つような部分グラフH
• 固定したγに対して、極大局所／大域(k,γ)-trussを見つけたい

局所確率的truss分解

• $$ \sigma_G(e,t) = \Pr[\sup_G(e) \geq t] $$

1. k ← 2 to n
   1. $$ \sigma(e,k-1)p(e) < \gamma \wedge \sigma(e,k-2)p(e)\geq \gamma $$な辺eがあれば
   2. eのスコア=k
   3. eを削除して、eを含む△を消すことで影響するσを色々と更新

• $$ \Pr[\sup_G(uv) = t] $$の計算
  • $$ w \in N(u) \cap N(v) $$について、△={u,v,w}がある
  • △同士は独立（uvが生起する条件付けで）なので、そのうちt個の△が生きる確率はDPで計算出来る
• $$ \sigma(e,t) $$は計算した値の和をとればOK
• アルゴリズム中で△を消したときの更新は何か頑張れば出来る

大域確率的truss分解

• $$ \alpha_k(H,e) $$の厳密計算は#P-hard
• ランダムサンプリングしま～す。
• 何か色々とやっている
  • 各kについて含む△が少ない辺を消す
  • 各連結成分について探索を走らせる
    • Top-down exact: 普通に各辺除去していく
    • Bottom-up heuristic: 各辺から始めて適当に足していく

実験

• そこそこの速度で良さげな成分がとってこれました！

まとめ

• 普通。可もなく不可もなし。

SIGMOD k-truss uncertain graphs

2017/06/18