Archive for the ‘interesting reserch’ Category
Graph clustering algorithm
June 30, 2010
Leave a comment
首先这是个经典的问题,但是一些算法看了还是似懂非懂,基础差是问题所在。
我看到方法主要分为两类:
- Graph partitioning based on minimum cut or spectral partitioning. 简单说就是最小化不同簇之间的连接. 详细参考 http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html 这种方法存在一些不足,它一次只能二分,对于不知道能聚成多少的类的情况,如果采用多次二分方法,最小化簇之间的连接并不是个好的准则。 感觉二分的思想还是很精妙的,使用线性代数矩阵的知识,数学支撑还是很强。
- 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
这些算法都比较耗时,复杂度高,遇到大规模数据时就麻烦啦。
Categories: interesting reserch
algorithm