Year: 2015
Author: K.C. Chang, Sihong Shao, Dong Zhang
Journal of Computational Mathematics, Vol. 33 (2015), Iss. 5 : pp. 443–467
Abstract
This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend (CD) framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power (IP) method and the steepest descent (SD) method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1506-m2014-0164
Journal of Computational Mathematics, Vol. 33 (2015), Iss. 5 : pp. 443–467
Published online: 2015-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 25
Keywords: Spectral graph theory Spectral clustering 1-Laplace operator Graph Laplacian Eigenvalue problems Cheeger constant Graph cut Optimization Convergence