Home > sgwt_toolbox > sgwt_laplacian.m

sgwt_laplacian

PURPOSE ^

sgwt_laplacian : Compute graph laplacian from connectivity matrix

SYNOPSIS ^

function L = sgwt_laplacian(A,varargin)

DESCRIPTION ^

 sgwt_laplacian :  Compute graph laplacian from connectivity matrix

 function L = sgwt_laplacian(A,varargin)

 Connectivity matrix A must be symmetric.  A may have arbitrary
 non-negative values, in which case the graph is a weighted
 graph. The weighted graph laplacian follows the definition in
 "Spectral Graph Theory" by Fan R. K. Chung

 Inputs :
 A - adjacency matrix
 Selectable Input parameters :
 'opt' - may be 'raw' or 'normalized' (default raw) to select
         un-normalized or normalized laplacian

 Outputs : 
 L - graph Laplacian

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 % sgwt_laplacian :  Compute graph laplacian from connectivity matrix
0002 %
0003 % function L = sgwt_laplacian(A,varargin)
0004 %
0005 % Connectivity matrix A must be symmetric.  A may have arbitrary
0006 % non-negative values, in which case the graph is a weighted
0007 % graph. The weighted graph laplacian follows the definition in
0008 % "Spectral Graph Theory" by Fan R. K. Chung
0009 %
0010 % Inputs :
0011 % A - adjacency matrix
0012 % Selectable Input parameters :
0013 % 'opt' - may be 'raw' or 'normalized' (default raw) to select
0014 %         un-normalized or normalized laplacian
0015 %
0016 % Outputs :
0017 % L - graph Laplacian
0018 
0019 % This file is part of the SGWT toolbox (Spectral Graph Wavelet Transform toolbox)
0020 % Copyright (C) 2010, David K. Hammond.
0021 %
0022 % The SGWT toolbox is free software: you can redistribute it and/or modify
0023 % it under the terms of the GNU General Public License as published by
0024 % the Free Software Foundation, either version 3 of the License, or
0025 % (at your option) any later version.
0026 %
0027 % The SGWT toolbox is distributed in the hope that it will be useful,
0028 % but WITHOUT ANY WARRANTY; without even the implied warranty of
0029 % MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0030 % GNU General Public License for more details.
0031 %
0032 % You should have received a copy of the GNU General Public License
0033 % along with the SGWT toolbox.  If not, see <http://www.gnu.org/licenses/>.
0034 
0035 function L = sgwt_laplacian(A,varargin)
0036   control_params={'opt','raw'}; % or normalized
0037   argselectAssign(control_params);
0038   argselectCheck(control_params,varargin);
0039   argselectAssign(varargin);
0040   
0041   N=size(A,1);
0042   if N~=size(A,2)
0043     error('A must be square');
0044   end
0045   degrees=vec(full(sum(A)));
0046   % to deal with loops, must extract diagonal part of A
0047   diagw=diag(A);
0048   
0049   % w will consist of non-diagonal entries only
0050   [ni2,nj2,w2]=find(A);
0051   ndind=find(ni2~=nj2); % as assured here
0052   ni=ni2(ndind);
0053   nj=nj2(ndind);
0054   w=w2(ndind);
0055   
0056   di=vec(1:N); % diagonal indices
0057   
0058   switch opt
0059    case 'raw'
0060     % non-normalized laplacian L=D-A
0061     L=sparse([ni;di],[nj;di],[-w;degrees-diagw],N,N);
0062    case 'normalized'
0063     % normalized laplacian D^(-1/2)*(D-A)*D^(-1/2)
0064     % diagonal entries
0065     dL=(1-diagw./degrees); % will produce NaN for degrees==0 locations
0066     dL(degrees==0)=0;% which will be fixed here
0067     % nondiagonal entries
0068     ndL=-w./vec( sqrt(degrees(ni).*degrees(nj)) );
0069     L=sparse([ni;di],[nj;di],[ndL;dL],N,N);
0070    otherwise
0071     error('unknown option');
0072   end

Generated on Tue 04-May-2010 16:00:20 by m2html © 2003