function [ C, L, D, Q, V ] = SpectralClustering(W, k)
%||||||||||||||||||||||||||||||||||||||||||| Note ||||||||||||||||||||||||||||||||||||||||||
% spectral clustering algorithm
% input: adjacency matrix W; number of cluster k
% return: cluster indicator vectors as columns in C; unnormalized Laplacian L;
% degree matrix D; eigenvectors matrix Q; eigenvalues matrix V
%//////////////////////////////// Body ////////////////////////////////////
% calculate degree matrix
degs = sum(W, 2);
D = sparse(1:size(W, 1), 1:size(W, 2), degs); % sparse matrix
% compute unnormalized Laplacian
L = D - W;
% compute the eigenvectors corresponding to the k smallest eigenvalues
% diagonal matrix V is Ncut L's k smallest magnitude eigenvalues
% matrix Q whose columns are the corresponding eigenvectors.
[Q1, V1] = eigs(L, k+1, 'SA'); % min eigenvalue == 0
v = diag(V1);
V = diag(v(2:end));
Q = Q1(:,2:end);
% use the k-means algorithm to cluster V row-wise
% C will be a n-by-1 matrix containing the cluster number for each data point
C = kmeans(Q, k);
% convert C to a n-by-k matrix containing the k indicator vectors as columns
C = sparse(1:size(D, 1), C, 1);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function C = SpectralClustering(W, k)
% [n,m] = size(W)
% s = sum(W);
% D = full(sparse(1:n, 1:n, s));
% E = D^(-1/2)*W*D^(-1/2);
% [Q, V] = eigs(E, k);
% C = kmeans(Q, k);
% end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% [Q1,V1] = eig(L);
% m = size(L,1);
% Q = zeros(m,k);
% diag_e = diag(V1);
% element = sort( diag_e );
%
% if ( diag_e(1)<1e-10 )
% for i = 2:( k+1 )
% v(i-1) = element(i);
% idx = find( diag_e == v(i-1),1);
% Q(:,i-1) = Q1(:,idx);
% end
% else
% for i = 1:k
% v(i) = element(i);
% idx = find( V1 == v(i),1);
% Q(:,i) = Q1(:,idx);
% end
% end
% V = diag(v);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%