Online Search of Overlapping Communities (SIGMOD'13)

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