Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local ... - todo314 @ ウィキ

Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local Community Methods

• David F. Gleich, Seshadhri Comandur
  • せしゃどり
• In KDD 2012

(closed) vertex neighbor

• 距離1以内の頂点集合
• これがそれなりに良いコミュニティ
  • マジかよ
  • 理論的に示す
• 実データも使う

目的関数

• $$ vol(S) = \sum_{v \in S} \deg(v) $$
• $$ cut(S,T) = \{ (u, v) \in E | u \in S, v \in T \} $$
• コンダクタンス（これが目的関数）
  • $$ \Phi(S) = cut(S, V \setminus S) / \min(vol(S), vol(V \setminus S)) $$

定理

• コンダクタンスが高々4(1-κ)/(3-2κ)のneighbor cutがある
  • κ: グローバルクラスタ係数
  • κ>=1/2じゃないと意味が無い（自明）
  • 次数分布の仮定無し
• 証明は簡単らしい(probabilistic method)
• power-lawを仮定すると
  • k-core(κ d_max^β)が存在する

実験

• ほとんどのデータセットはκ<1/2

比較対象

• Fiedler Cut
• personalized PageRank community
  • Random walk with restartのようなもの
• whisker
• METIS

結果

• びみょう～～～

応用？

• seed set
  • これを拡張してクラスタを構成する
• これを見つけるのがめんどい
  • Leskovec, et al.’09 ←ちぇっく！
• どの近傍よりもコンダクタンスが小さい頂点を選ぶ
• で、近傍がある程度たくさんあるものをseedとする

結果

• seedとしてコミュニティを求めるのといい感じなんですか？
• はやお

KDD community detection

2013-10-31 17:05:36 (Thu)