Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with ... - todo314 @ ウィキ

Denser than the Densest Subgraph: Extracting Optimal Quasi-Cliques with Quality Guarantees

• Charalampos E. Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, Maria A. Tsiarli
• In KDD 2013
• http://www.math.cmu.edu/~ctsourak/kdd13.pptx

概要

• quasi-clique の評価関数を変えた
• densest-graphの評価関数 $$ e[S]/|S| $$ はだめ！
  • 辺密度が低いし（グラフがでかいから）、直径もでかい
• 辺密度: $$ e[S]/{|S| \choose 2} $$は
• 貪欲アルゴリズムと局所探索を提案

評価関数

• edge-surplus
• $$ f_\alpha = g(e[S]) - \alpha h(|S|) $$
  • g,hは適当に決める
• 上の評価関数はf,gを適当に決めれば良い

OQC-problem

定義

• $$ \mbox{maximize} f_\alpha(S) = e[S]-\alpha {|S| \choose 2} $$

性質

• NP-hard
  • せやな
• αの値によってはいいことがおこる
  • >= 1/3なら
  • 非連結な頂点集合2つあったときに、それらをマージすると、評価関数が下がる
    • quasi-cliqueとしては自然な性質

アルゴリズム

貪欲近似アルゴリズム

• 一番次数が小さい頂点を取り除く
• 一番評価関数が大きかったものを出力
• 線形時間
• additive approximation

局所探索

変種

top-k optimal quasi-cliques

• 互いに素なquasi-cliquesをk個選ぶ
  • 繰り返し実行

contrained optimal quasi-cliques

• 頂点集合Qを∈quasi-cliqueで評価値がもっともよいもの
• NP-hard

実験

データセット

• 小さのから大きいのまで15種類
  • |V|:数十から数M、|E|:数百から数十M
• 種類もいろいろ

手法

• densest subgraph
• quasi-clique by greedy
• quasi-clique by local search

評価基準

• 頂点数
• 辺密度
• 直径
• 三角形密度
  • $$ t[S]/{|S| \choose 3} $$

結果

• 大きくない
• 密度も高い
• 直径が1~3におさまっている

KDD quasi-clique

2013-10-10 13:46:49 (Thu)