mloss.org 1SpectralClusteringhttp://mloss.orgUpdates and additions to 1SpectralClusteringenMon, 27 Jun 2011 10:45:57 -00001SpectralClustering 1.1http://mloss.org/software/view/287/<html><p>1-Spectral Clustering is a graph-based clustering method which relaxes the NP-hard problem of finding the optimal balanced cut of a similarity graph to a nonlinear eigenproblem involving the eigenvectors of the nonlinear graph 1-Laplacian.
</p>
<p>In contrast to the standard spectral relaxation, this relaxation is tight in the sense that the second eigenvalue of the (normalized) graph 1-Laplacian is equal to the optimal (normalized) ratio Cheeger cut and the second eigenvector is the indicator function of the optimal partition.
</p>
<p>We use our nonlinear inverse power method to compute a nonconstant eigenvector of the graph 1-Laplacian. Note that convergence to the second eigenvector is not guaranteed but we can guarantee that the bipartitioning of 1-Spectral Clustering is at least as good as the one of Spectral Clustering and empirically it is in general much better.
</p>
<p>1-Spectral Clustering supercedes our previous p-Spectral Clustering, as 1-Spectral Clustering is much faster and yields better cuts. As the underlying optimization method is based on a first order method, the method easily scales to large sparse graphs (more than 100000 vertices).
</p></html>matthias hein, thomas buehlerMon, 27 Jun 2011 10:45:57 -0000http://mloss.org/software/rss/comments/287http://mloss.org/software/view/287/spectral clusteringclusteringgraph partitioning