16. Network community detection: Trawling and Spectral Clustering
Method: Trawling
小さいコミュニティ.人々,トピックを考える.密な二部グラフは,集団が同じことを考えているということでコミュニティだ.(→ HITS)
- 完全二部グラフを列挙する
- それを用いて密な二部グラフを列挙する
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 次元の直交基底により新しく埋めこまれた空間,すごく良いらしい