Graph clustering algorithm

首先这是个经典的问题，但是一些算法看了还是似懂非懂，基础差是问题所在。

我看到方法主要分为两类：

1. Graph partitioning based on minimum cut or spectral partitioning. 简单说就是最小化不同簇之间的连接.   详细参考 http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html 这种方法存在一些不足，它一次只能二分，对于不知道能聚成多少的类的情况，如果采用多次二分方法，最小化簇之间的连接并不是个好的准则。  感觉二分的思想还是很精妙的，使用线性代数矩阵的知识，数学支撑还是很强。
2. Modularity    基本思想是“There must be a smaller than expected number edges between communities”，
   Define modularity to be Q = (number of edges within groups) – (expected number within groups). 详细google ” Modularity and community structure in networks“

实现这些算法感觉挺难的，幸好有些开源的包，比如matlab中就有、Graclus software、Graph Clustering

这些算法都比较耗时，复杂度高，遇到大规模数据时就麻烦啦。