16. Network community detection: Trawling and Spectral Clustering

Method: Trawling

小さいコミュニティ.人々,トピックを考える.密な二部グラフは,集団が同じことを考えているということでコミュニティだ.(→ HITS)

  1. 完全二部グラフを列挙する
  2. それを用いて密な二部グラフを列挙する
Frequent Itemset Enumeration [Agrawal-Srikant'99]

The Apriori Algorithm.サイズ 1 のものを列挙.サイズ 2 のものを列挙,サイズ 3...

K_{s,t} to Communities

定理.二部グラフ.平均次数 $\overline{k}=s^\frac1t n^{1-\frac1t}+t$ なら $K_{s,t}$ が部分グラフとして含まれる.

(具体的にそのあとどうするのかは話なし)

Spectral Graph Partitioning

  • min-cut → あまりにもバランスが取れず悲しい (degenerate case)
  • そこで normalized-cut

Specgrap Graph Partitioning

k-Way Spectral Clustering

複数の固有ベクトルを使う

  • [Shi-Malik'00] Optimal k-way normalized cut の近似になっているらしい
  • Well-Separated Space
    • k 次元の直交基底により新しく埋めこまれた空間,すごく良いらしい