Multi-way clustering and biclustering by the Ratio cut and Normalized cut in graphs

作者：Fan Neng; Pardalos Panos M^*

来源：Journal of Combinatorial Optimization, 2012, 23(2): 224-251.

DOI：10.1007/s10878-010-9351-5

• Ratio cut
• Normalized cut
• Clustering
• Biclustering
• Graph partitioning
• Spectral relaxation
• Semidefinite programming
• Quadratically constrained programming

In this paper, we consider the multi-way clustering problem based on graph partitioning models by the Ratio cut and Normalized cut. We formulate the problem using new quadratic models. Spectral relaxations, new semidefinite programming relaxations and linearization techniques are used to solve these problems. It has been shown that our proposed methods can obtain improved solutions. We also adapt our proposed techniques to the bipartite graph partitioning problem for biclustering.

• 出版日期2012-2