The K-clique Densest Subgraph Problem - todo314 @ ウィキ

The K-clique Densest Subgraph Problem

• Charalampos E. Tsourakakis
• WWW 2015

概要

• 平均k-clique数最大の部分グラフ
• k=2: densest subgraph
• k=3: $$ \frac{\# \Delta(S)}{|S|} $$
• 厳密多項式時間アルゴリズム（k定数）
• 効率的1/k-近似アルゴリズム
• 実験: 3-clique densestの解はnear-clique

動機づけと問題定式化

• 例えば辺密度$$ \frac{e(S)}{{|S| \choose 2}} $$はどうですか？
  • 単一辺が最適なので意味無し
• 最密部分グラフはどうですか？
  • 解けるけど、本当に欲しいのはlarge near-clique
• 効率的に解ける定式化をします！
• $$ \frac{t(S)}{|S|} $$を最大化して下さい

提案手法

厳密アルゴリズム1

• Goldbergの最密部分グラフアルゴリズムの適応
• 二部グラフを作ります
  • 左がV(G)、右がT(G)
• 二分探索の回数は？
  • 差が1/n(n-1)以下になったら終了でOK
• $$ O(m^{3/2} + (nt+\min\{n,t\}^3)\log n) $$ 時間

厳密アルゴリズム2

• f(S)=t(S)-α|S|は優モジュラ関数
• f(S)を最大化（つまり、劣モジュラ関数最小化）＋αで二分探索でOK
• △を列挙しなくて良いので、O(n+m)空間
• 多項式時間だけど現実的には厳しそう

近似アルゴリズム

• #△最小の頂点を順に取り除いていく
• 適当実装でも、O(nm)時間
• MapReduce実装もあるけど省略

k-clique densest subgraph

• 似たような二部グラフ構築で解ける。
• 質的な話：k=4にすると結構すごいけど、k=2➔k=3程の差では無い

実験

• DS, 1/2-DS, TDS, 1/3-TDSを比較してみる
  • 頂点数、平均次数、辺密度、#△を見てみる
  • TDSの方が辺密度が高い、けど、そこそこ頂点数が多いので、意味がある
  • 近似と厳密にそれ程の差がない
• 一応MapReduceの方の実装もしているっぽい

まとめ

• かなりアルゴリズム寄りだけど、概念自体はかなり分かりみがある
• もうちょい出力を制御出来たら嬉しい

WWW 密部分グラフ

2017/05/27