compute_graph_laplacian.m
bdfe7aadccccmaster

compute_graph_laplacian.m
View Options


			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Author:
			% Xavier Bresson, xavier.bresson@epfl.ch
			%
			% Course:
			% A Network Tour of Data Science
			% a.k.a. Graph Algorithms in Data Science
			% EPFL, Fall 2015
			%
			% Version:
			% September 23, 2015
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Graph Laplacian Operator
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			% Usages:
			% L = compute_graph_laplacian(W); % compute normalized graph Laplacian
			% L = compute_graph_laplacian(W,'unnormalized'); % compute UNnormalized graph Laplacian
			%
			% Notations:
			% n = nb_data
			%
			% Input variables:
			% W = Adjacency matrix. Size = n x n.
			%
			% Output variables:
			% L = Graph Laplacian. Size = n x n.
			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

			function L = compute_graph_laplacian(W,type_laplacian)

			tstart = tic;

			if nargin==1
			type_laplacian = 'normalized';
			else
			type_laplacian = 'UNnormalized';
			end


			if strcmp(type_laplacian,'normalized')

			% Normalized Laplacian
			n = size(W,1);
			D = sum(W,2)+eps;
			invDhalf = spdiags(1./sqrt(D),0,n,n);
			L = speye(n) - invDhalfWinvDhalf;
			L = sparse(L);

			fprintf('\nComputational time for normalized graph Laplacian (sec) = %.3f\n\n',toc(tstart));

			elseif strcmp(type_laplacian,'UNnormalized')

			% Unnormalized Laplacian
			n = size(W,1);
			D = sum(W,2);
			D = spdiags(D,0,n,n);
			L = D - W;
			L = sparse(L);

			fprintf('\nComputational time for unnormalized graph Laplacian (sec) = %.3f\n\n',toc(tstart));

			end

			end