Querying K-Truss Community in Large and Dynamic Graph (SIGMOD'14)

• 問題
  • グラフ G，クエリ：頂点 v, 整数 k
  • v を含む k-truss community をすべて列挙
• k-truss vs. clique percolation
  • clique percolation: コミュニティと呼べない，パラメータが３つも，NP-Hard
  • k-truss: コミュニティの直径が |C|/k，高枝連結度，パラメタ１つ，多項式時間
• index
  • simple index
    • 各枝の trussness を計算しておく
  • tcp index (tcp = triangle connectivity preserved)
    • simple の無駄：要らない枝へのアクセス，使用する枝への複数回のアクセス
    • 各頂点について近傍のみからなるグラフを考え，最大全域森を取る
    • うまいこと近傍のみからなるグラフを移りながら探索する
• dynamic update
  • 下界だか上界だかを使って処理を枝刈りするらしい