読者です 読者をやめる 読者になる 読者になる

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]