On Triangulation-based Dense Neighborhood Graph Discovery - todo314 @ ウィキ

On Triangulation-based Dense Neighborhood Graph Discovery

• Nan Wang, Jingbo Zhang, KianLee Tan, Anthony K. H. Tung
• VLDB 2011

概要

• 僕の考えた最強のdense graph
• 任意の2頂点が共有する近傍がλ個以上
• そこそこいい性質を持っている（らしい）
• triangulationを上手く使って、検出

DN-graph

• λ(V')
  • 頂点対が共有する近傍の数の最小値
• Dense Neighborhood graph
• G'=(V',E')について
  1. 任意の2頂点はλ個以上の近傍を共有している
  2. λ(V'∪{v})<λ, λ(V'-{v})≦λ
• DN-graphs g(v,e,λ)を全部見つけたい
• λ(e): eを含むようなG'のλ(G')の最大値
• Theorem 3.1.
  • G'がDN-graph⇔
  • G'内の各辺eはλ(e)=λ_maxを満たす
  • G'の近傍uとG'内の点vについて、λ(u,v)≦λ_max
  • 自分の疑問: ≦じゃなくて＜な気がするけど違うのかな？
• つまり？
  • λ(e)が全部分かったら、λ(e)の同じ辺を繋いでいけば良い
• λ(e)の計算は大変なので、その上限を「eを含む三角形の個数」でとりあえず与える

Triangulationを使った検出

• Proposition 4.1.
  • wがuvをsupport
    • λ~(u,v)≦min{λ~(u,w), λ~(v,w)}
  • uvをsupportするwがλ~(u,v)個以上あったらλ~(u,v)はvalid
• TriDN
  • eをsupportする頂点の数でλ~(e)をbound、これを更新できるだけ繰り返す
• BiTri
  • λ(e)のboundを二分探索で頑張るらしい
• StreamDN
  • semi-streamingな感じ
  • 大変だ
  • error-boundはできるらしい

実験

• TriDNはBiTriDNよりかなり遅い
• というか終わらんケースがある、BiTriDNは20反復位で終わる
• Flickr(|V|=1.7M, |E|=23M) にBiTriDNを適用
  • 1時間/反復×66反復
  • 最大のλは278

まとめ

• こういう設定は他のよく分からん辺密度の適当な式よりマシだと思った
• 性質が面白そうだけど、これだけだと微妙そう
• もっとタイトにしなくていいのかな？近似とか

VLDB 三角形 密部分グラフ

2014-09-09 02:07:16 (Tue)