On triangulation-based dense neighborhood graph discovery

Nan Wang, Jingbo Zhang, Kian-Lee Tan, and Anthony K. H. Tung. 2010. On triangulation-based dense neighborhood graph discovery. Proc. VLDB Endow. 4, 2 (November 2010), 58-68.

内容

• dense な部分グラフをとりたいね．
• いろんなのあるけど DN-Graph というのはどうか（提案）
• DN-Graph with parameter λ とは，部分グラフであって，
  • 任意の二頂点は近傍をλ以上共有
  • 任意の外の頂点を付け加えるとそれがλ未満になっちゃう
  • 任意の中の頂点をとっぱらうとそれがλ未満になっちゃう
• クリークとか帰着できて NP-Hard なので適当にやるしかない
• アルゴリズム
  • よく分からん（めんどい）
• 実験は最大で Flickr (1.7M 頂点, 22.6M 辺)．1 時間とか．

感想

NP-Hard とはいえこういうグラフからクリークを探すのは実際にはサブエクスポネンシャルになって結構大規模なグラフでも凄い早いので，それで NP-Hard っていうのはどのぐらい意味を持つのかよくわからん

O(3|V| + 3|E|) とかいう記法が現れてどん引きだった（何を言っているんだ）