Querying K-Truss Community in Large and Dynamic Graph - todo314 @ ウィキ

Querying K-Truss Community in Large and Dynamic Graph

• Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, Jeffrey Xu Yu
• SIGMOD 2014

• (α, γ)-OCS
  • γ-quasi-k-クリークを頂点とする
    • γ{k choose 2}本以上のk頂点部分グラフ
  • ↑を各頂点として，α頂点以上共有なら辺を張る
  • ヘボい！

• k-truss
  • どの辺も少なくともk-2個の三角形に属する極大な部分グラフ
  • 辺の連結: どの2辺も三角形の連結で到達可能

• k-truss コミュニティ
  • vを含むk-truss コミュニティを列挙

• 利点
  • パラメタが1つ
  • 多項式時間

• k-truss コミュニティクエリ
  • 2つの索引
  • Simple index, Novel index

• 性質
  • ある辺を含むk-truss コミュニティは唯一

• Simple Index
  • τ(e) := eを含む部分グラフでeの属する三角形の数がτ(e)以上，みたいな を計算
  • τ(e)を全部計算
  • クエリの答え方
    • vを端点とする辺からτ(e)≧kとなるように三角形をたどっていく
    • 早そう

• Novel Index
  • τ(e)<kにアクセスするのが無駄

SIGMOD k-truss 動的グラフ

2014/12/06