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: コミュニティと呼べない,パラメータが3つも,NP-Hard
    • k-truss: コミュニティの直径が |C|/k,高枝連結度,パラメタ1つ,多項式時間
  • index
    • simple index
      • 各枝の trussness を計算しておく
    • tcp index (tcp = triangle connectivity preserved)
      • simple の無駄:要らない枝へのアクセス,使用する枝への複数回のアクセス
      • 各頂点について近傍のみからなるグラフを考え,最大全域森を取る
      • うまいこと近傍のみからなるグラフを移りながら探索する
  • dynamic update
    • 下界だか上界だかを使って処理を枝刈りするらしい