THESE/codes/graphe/Ncut_9/ncut.m

   1 function [Eigenvectors,Eigenvalues] = ncut(W,nbEigenValues,dataNcut);\r
   2 % function [Eigenvectors,Eigenvalues] = ncut(W,nbEigenValues,dataNcut);\r
   3 % \r
   4 % Input:\r
   5 %     W= symmetric similarity matrix\r
   6 %     nbEigenValues=  number of Ncut eigenvectors computed\r
   7 %     dataNcut= optional parameters\r
   8 %\r
   9 %     default parameters for dataNcut:\r
  10 %     dataNcut.offset = 5e-1; offset in the diagonal of W\r
  11 %     dataNcut.verbose = 0; 0 for verbose off mode, 1,2,3 for verbose on modes\r
  12 %     dataNcut.maxiterations = 100; max number of iterations in eigensolver\r
  13 %     dataNcut.eigsErrorTolerance = 1e-6; error tolerance in eigensolver\r
  14 %     dataNcut.valeurMin=1e-6; % truncates any values in W less than valeurMin\r
  15 % \r
  16 % Output: \r
  17 %    Eigenvectors= continuouse Ncut eigenvectos, size = length(W) x nbEigenValues\r
  18 %    Eigenvalues= Ncut eigenvalues, size = 1x nbEigenValues\r
  19 %\r
  20 % Timothee Cour, Stella Yu, Jianbo Shi, 2004.\r
  21 \r
  22 if nargin < 2\r
  23     nbEigenValues = 8;\r
  24 end\r
  25 if nargin < 3\r
  26     dataNcut.offset = 5e-1;\r
  27     dataNcut.verbose = 0;\r
  28     dataNcut.maxiterations = 300;\r
  29     dataNcut.eigsErrorTolerance = 1e-8;\r
  30     dataNcut.valeurMin=1e-6;\r
  31 end\r
  32 % if nargin < 3\r
  33 %     dataNcut.offset = 5e-1;\r
  34 %     dataNcut.verbose = 0;\r
  35 %     dataNcut.maxiterations = 100;\r
  36 %     dataNcut.eigsErrorTolerance = 1e-6;\r
  37 %     dataNcut.valeurMin=1e-6;\r
  38 % end\r
  39 \r
  40 % make W matrix sparse\r
  41 W = sparsifyc(W,dataNcut.valeurMin);\r
  42 \r
  43 % check for matrix symmetry\r
  44 if max(max(abs(W-W'))) > 1e-10 %voir (-12) \r
  45     %disp(max(max(abs(W-W'))));\r
  46     error('W not symmetric');\r
  47 end\r
  48 \r
  49 n = size(W,1);\r
  50 nbEigenValues = min(nbEigenValues,n);\r
  51 offset = dataNcut.offset;\r
  52 \r
  53 \r
  54 % degrees and regularization\r
  55 d = sum(abs(W),2);\r
  56 dr = 0.5 * (d - sum(W,2));\r
  57 d = d + offset * 2;\r
  58 dr = dr + offset;\r
  59 W = W + spdiags(dr,0,n,n);\r
  60 \r
  61 Dinvsqrt = 1./sqrt(d+eps);\r
  62 P = spmtimesd(W,Dinvsqrt,Dinvsqrt);\r
  63 clear W;\r
  64 \r
  65 options.issym = 1;\r
  66      \r
  67 if dataNcut.verbose\r
  68     options.disp = 3; \r
  69 else\r
  70     options.disp = 0; \r
  71 end\r
  72 options.maxit = dataNcut.maxiterations;\r
  73 options.tol = dataNcut.eigsErrorTolerance;\r
  74 \r
  75 options.v0 = ones(size(P,1),1);\r
  76 options.p = max(35,2*nbEigenValues); %voir\r
  77 options.p = min(options.p,n);\r
  78 \r
  79 %warning off\r
  80 % [vbar,s,convergence] = eigs2(@mex_w_times_x_symmetric,size(P,1),nbEigenValues,'LA',options,tril(P)); \r
  81 [vbar,s,convergence] = eigs_new(@mex_w_times_x_symmetric,size(P,1),nbEigenValues,'LA',options,tril(P)); \r
  82 %warning on\r
  83 \r
  84 s = real(diag(s));\r
  85 [x,y] = sort(-s); \r
  86 Eigenvalues = -x;\r
  87 vbar = vbar(:,y);\r
  88 Eigenvectors = spdiags(Dinvsqrt,0,n,n) * vbar;\r
  89 \r
  90 for  i=1:size(Eigenvectors,2)\r
  91     Eigenvectors(:,i) = (Eigenvectors(:,i) / norm(Eigenvectors(:,i))  )*norm(ones(n,1));\r
  92     if Eigenvectors(1,i)~=0\r
  93         Eigenvectors(:,i) = - Eigenvectors(:,i) * sign(Eigenvectors(1,i));\r
  94     end\r
  95 end\r