Online Search of Overlapping Communities (SIGMOD'13)

  • 問題
    • 頂点 v, k が与えられるので,v を含む k-clique percolation (的なもの) を即返す
    • 前処理なし
    • (この問題を考えたこと自体が貢献)
  • 拡張した k-clique percolation
    • (α, γ)-OCS: γ-quasi k-clique,α頂点共有なら枝を張る
  • アルゴリズム
    • 普通に探索する
    • 近似アルゴリズムというのもある
  • 実験結果
    • random 100 はずるい
    • コミュニティ数 0 の時の精度はどうしているのか?