The K-clique Densest Subgraph Problem (WWW '15)

Tsourakakis, Charalampos E

概要

多くの応用ではクリークに似た大きな部分グラフを見つけたい。適当に定式化するとMaximum-Clique問題との関係でNP-hardになってしまい近似計算すら難しくなってしまう。一方densest subgraphは多項式時間で検出するアルゴリズムが知られているが得られた部分グラフはクリークと比べると非常に疎であることが多い。

この論文ではdensest subgraphを一般化したk-clique densest subgraph問題というものを提案する。与えられたグラフ \(G = (V, E) \)に対して\(argmax_{S \subseteq V} \frac{t_k(S)}{|S|} \)を求めるのがk-clique densest subgraphである。\(t_k(S) \)はSに誘導される部分グラフに内部のk-cliqueの個数. \(k=2 \)のときこれはdensest subgraphと一致する。\(k = 3 \)のとき、すなわち三角形を含む割合が最も高い部分グラフで面白い結果がでるらしい。

このk-clique densest subgraphというのはdensest subgraphと同様に多項式時間で計算することができ、\(\frac{1}{k} \)近似の高速なアルゴリズムある。厳密な計算を高速に行うためにはMap-reduceを利用している。

Footballというグラフにおいてdensest subgraphと\(k = 3 \)でのk-clique densest subgraphを求めた結果、densest subgraphではグラフ全体を出力してしまい辺密度\(\frac{|E(S)|}{|S| \times (|S| - 1) \div 2 } \)が0.1くらいしかなかったがk-clique densest subgraphによってもとまった18頂点からなる部分グラフは辺密度が0.5くらいありかなりcliqueに近かった。

実際の応用例についても示したらしいがそこは読んでない。