Sampling Community Structure

WWW 2010. http://arun.maiya.net/papers/maiya_etal-sampcomm.pdf

大きいグラフに対する計算は時間がかかる．サンプリングしてからなにかするのはどうか．特に，今回の目的はコミュニティ構造の検出．

イントロダクション

既存

• [KDD'06] 一般的なグラフサンプリング．次数分布，クラスタ係数．
• [ICDM'08] 次数分布，クラスタ係数．より良い精度，state-of-the-art．
• これらの指標だけ保ってればいいのか？

本論文

• 新しいサンプリングの良さ．
• 提案手法
  • snowball expansionsampler (XSN)
  • MCMC expansion sampler (XMC)
• 実験的に優位性を示した

問題

誘導部分グラフであって，コミュニティの分割のされ方が同じようなものを作りたい．

• P(G)，P(G[S]) を比較した F 値（2*recall*precision / (recall+precision))
  • recall: 一頂点でもあらわれてるものが何個出てくるか
  • precision: partition-distance = 分割が同値になるために除くべき最小の頂点数 D．1 - D/|S|．

提案手法

アイディア

• $ S \subseteq V $ の expansion factor $X(S) := |N(S)| / |S|$
  • $ N(S) := $ 隣接点 $\setminus S$
• maximum expander, $argmax_{|S|=k} X(S) $ を求めることを目指すらしい

なぜ？

• 順番に選ぶと思った時．覆われてない頂点を選ぶと良さそう．覆われてない頂点をたくさん覆う．手付かずのコミュニティが選ばれそう．

（疑問点：これが関係あるのって recall だけなんじゃ…）

アルゴリズム

NP 困難なのでヒューリスティクス．

• XSN: 始点を選ぶ．隣接点を貪欲に選ぶ．
• XMC: ランダムな S から開始．変更して，良かったら採用，悪くても確率により採用 (MCMC)．

実験

• F 値，recall, precision
  • 15%．CNM アルゴリズム．
• 他の頂点の属するコミュニティの推定
  • weighted majority relational model [Mackassy07] を使う

どちらでも既存手法より良い．「『クラスタ係数がよければコミュニティ構造がよく表されている』という Jure さんの主張は嘘だ！」

後続の研究

[Maiya, KDD'11], [Satuluri, SIGMOD'11]