Sampling Community Structure - todo314 @ ウィキ

Sampling Community Structure

• Arun S. Maiya, Tanya Y. Berger-Wolf
• WWW 2010

概要

• expander graphのコンセプトによるコミュニティのサンプリング手法
• コミュニティ検出で推論っぽいこと？もできるらしい

問題

• X(S) = |N(S)|/|S|
  • 隣接頂点数/頂点数
• サイズkのサンプルSがcommunity representative sample
  • minimize D[P_S(G(S)), P_S(G)]
    • D[,]は分割に対する距離尺度
    • P_S(G)はGを使って作られた分割

手法

• X(S)の最小化もあるけれどそうではなくて、最大のサンプルを見つけたい
• 2つ手法を考えたよ

Snowball Expansion Sampler (XSN)

• 最初の頂点を適当に選ぶ
• k個選ぶまで、|N({v})-(N(S)∪S)|が最大の頂点をSに追加
  • 何でこの式なのかは何か説明されている
• つまり単にX(S)についてGreedyするだけ

MCMC (XMC)

• Markov Chain Monte Carlo simulation
• |N(S)|/|V-S|をスコアとする
• スコアがよくなったら更新、悪くなったら[新しいスコア/今のスコア]^pみたいな確率で更新

実験

• コミュニティ検出手法
  • Girvan-Newman algorithm (GN)
  • Newman’s leading eigenvector method (NLE)
  • An algorithm based on greedy optimization (CNM)
• 評価基準
  • 分割の距離関数D
    • 分割が同一になるようにするために削除する頂点数の最小値
    • サンプルから出来たコミュニティの頂点達が元のでかいグラフから出来た同じコミュニティに入っていると良い
  • サンプル内のコミュニティの割合も考える
  • ↑2つを混ぜるよ
  • FRAC...recall
    • サンプル内のコミュニティの割合？？？（高いほうが良い
  • PART...precision
    • 距離関数の値を正規化して1-xを計算（高い方が良い
  • F-scoreを計算する
  • Composite = (2FRAC+PART)/(FRAC+PART)

結果

• XSNがかなりよさげ
  • FRACもPARTもCompositeも
• 次数分布とクラスタ係数も比べてみたお
  • べつにあんまり良くない

まとめ

• ふ～ん
• 理論的にどうこう無いし、気合いで説得なのかなあ？

WWW community detection

2013-12-31 19:17:44 (Tue)