A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem
-
Shweta Jain, C. Seshadhri
-
CoRR
概要
-
k-クリークの個数の数え上げ
-
サンプリングでの精度を上げるために、元のグラフをclique shadowと言うものに分解し、その上でサンプリング
-
shadowの良さをTuránの定理を使って与える←辺密度がある値以上
-
構築はクリーク探索の再帰的アルゴリズムを途中打ち切り
-
shadowの大きさは上手くバウンドできないけど、実際的にはかなり小さく上手く行く
Turán's theorem
-
k-cliqueの密度 $$ \rho_k(G) := |C_k(G)|/{|V| \choose k} $$
-
定理3.1 Turán
-
$$ \rho_2(H) > 1-\frac{1}{k-1} $$ならHはk-cliqueを含む
-
(k-1)-部グラフがタイトな例
-
定理3.2 Erdős
-
t頂点グラフHについて、
-
$$ \rho_2(H) > 1-\frac{1}{k-1} $$ならHはk-cliqueを$$ (t/(k-1))^{k-1} $$個以上のk-cliqueを含む
-
言い換え: $$ f(k)=k^{k-2}/k! $$とすると、$$ \rho_k(H) \geq 1/f(k)t^2 $$
Clique shadows
-
$$k$$-clique shadow $$ \mathbf{S} = \{ (S_i, \ell_i) \}_i $$
-
$C_k(G)$$と$$ \bigcup_{(S,\ell) \in \mathbf{S}}C_\ell(S) $$との間に全単射関係がある
-
multisetでも良い、$$(S,\ell)$$中の$$\ell$$-cliqueをかき集めると、G中のk-cliqueに対応する
-
$$\gamma$$-saturated: $$ \forall (S, \ell) \in \mathbf{S}, \rho_\ell(S) \geq \gamma $$
-
$$ \textsf{sample}(\mathbf{S},\gamma,k,\epsilon,\delta) $$
-
$$(S,\ell)$$ の確率分布$$\mathcal{D}$$ を $$ p(S) \propto {|S| \choose \ell} $$で定める
-
$$ \frac{20}{\gamma \epsilon^2} \log \delta^{-1} $$回繰り返し
-
$$ (S,\ell) $$を標本、Sから$$\ell$$-tuple Aを標本、Aが$$\ell$$-クリークなら、カウントインクリメント
-
カウントを適当に正規化し返す
-
時間$$ O(\mathrm{size}(\mathbf{S}) + \frac{1}{\gamma \epsilon^2} \log \delta^{-1}) $$
-
$$\gamma$$-saturatedなら $$ (1 \pm \epsilon) $$-近似 w.p. $$1-\delta$$
-
$$\gamma$$-saturatedってどうやって確認するの?←Erdősの定理3.2
-
定理4.4
-
$$ \rho_2(S) > 1-\frac{1}{\ell -1} $$なら、
-
$$ \gamma = 1/\max_{(S,\ell) \in \mathbf{S}}f(\ell) |S|^2 $$-saturated
Saturated clique shadowの構成
-
クリーク探索の伝統的なアルゴリズムを使う:
-
k-core分解な感じの向き付けをする
-
(S内のk-cliqueの個数) = (S中の点sの出近傍$$N_s^+$$内の(k-1)-cliqueの個数)の和
-
これを再帰的に実行する
-
今回は、
-
$$ \mathbf{T} = \{(V,k)\} $$から始めて、
-
$$ \rho_2(N_s^+) > 1-\frac{1}{\ell-2} $$なら打ち切って、$$ \mathbf{S} $$に$$(N_s^+,\ell-1)$$を追加
-
そうでないなら、$$ \mathbf{T} $$に$$(N_s^+,\ell-1)$$を追加
-
※$$ \mathbf{S} \cup \mathbf{T} $$は常にclique shadowで、$$ \mathbf{S} $$は常に$$\gamma$$-saturated
-
|S|がcore numberで抑えられるので、実行時間が$$ O(\alpha(G)\mathrm{size}(\mathbf{S})) $$と線形時間になる
-
size(S)は分からんが実際のグラフだと超小さい
実験
-
短めだけど、一通り調べている
-
誤差を小さく、既存手法を圧倒
-
shadowの大きさが大体グラフサイズに比例
-
クリーク数がkに応じて増えるグラフと減るグラフがある
まとめ
-
shadowの概念がかなり面白い
-
クリーク探索の再帰的アルゴリズムを知っていたら、確かにそうっぽい感じを受けるのだろうけど、
-
打ち切る条件をTurán's theoremでKOOLに定めている
-
こういう普通のサンプリングが上手く行かないので、非自明な工夫をするのは面白い
クリーク サンプリング
2017/01/01
最終更新:2017年01月01日 19:25