Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling - todo314 @ ウィキ

Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling

• Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos Tsourakakis, Shen Chen Xu
• KDD 2015

概要

• The K-clique Densest Subgraph Problemの後続
• k-クリーク密部分グラフをいい感じの二部グラフ構築＋疎化により爆速で解く
• 基本はランダムサンプリング
• 10~10000倍早くなった

$$(p,q)$$-clique densest subgraph

• $$\#(p,q)$$-clique/点数 を最大化したい

提案手法

二部グラフ構築

1. 実は(k-1)-cliqueでOK
2. ぶっちゃけ同じらしい

Densest subgraph sparsifier

• k-cliqueとか(p,q)-bicliqueを超辺に変換する
• $$ p_D = \frac{6\log n}{\epsilon^2 D} $$で各超辺をサンプルする
• W.h.p,
• $$ \rho(U) \geq D $$ なら $$ \tilde{\rho(U)}\geq(1-\epsilon)C \log n $$
• $$ \rho(U) < (1-2\epsilon)D $$ なら $$ \tilde{\rho(U)} < (1-\epsilon)C \log n $$
• 証明のアイデア
  • Pr[Uがやばい]$$\leq n^{-3|U|}$$
  • だから全部足しても以外と大事
• 大雑把な結論
  • 時間$$p_D$$倍、空間$${p_D}^2$$倍
    • 超辺をその場でサンプリングすればOK

実験

• p_Dとかεの値がイマイチ分かりにくい…
• kが大きい方が効果的
• k=3:数十倍、k=4:数百倍、k=5:数千倍以上

まとめ

• 結構すごい
• ρが小さいとあまり上手く行かなさそう
• そういう場合はそもそも意味が無いから大きいと仮定して良いのかな？

KDD 密グラフ 疎化

2017/06/11