「Vertex Neighborhoods, Low Conductance Cuts, and Good Seeds for Local ...」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
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 ←ちぇっく！
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としてコミュニティを求めるのといい感じなんですか？
- はやお
&tags()
&update()
