www.gusucode.com > matlab 案例源码 matlab代码程序 > matlab/PartitionGraphWithLaplacianMatrixExample.m
%% Partition Graph with Laplacian Matrix % This example shows how to use the Laplacian matrix of a graph to compute % the Fiedler vector. The Fiedler vector can be used to partition the graph % into two subgraphs. %% Load Data % Load the data set |barbellgraph.mat|, which contains the sparse adjacency % matrix and node coordinates of a barbell graph. load(fullfile(matlabroot,'examples','matlab','barbellgraph.mat')) %% Plot Graph % Plot the graph using the custom node coordinates |xy|. G = graph(A,'OmitSelfLoops'); p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.','MarkerSize',4.5); axis equal %% Calculate Laplacian Matrix and Fiedler Vector % Calculate the Laplacian matrix of the graph. Then, calculate the two % smallest eigenvalues and corresponding eigenvectors using |eigs|. L = laplacian(G); [V,D] = eigs(L,2,'sm'); %% % The Fiedler vector is the eigenvector corresponding to the second % smallest eigenvalue of the graph. The _smallest_ eigenvalue is zero, % indicating that the graph has one connected component. In this case, the % first column in |V| corresponds to the second smallest eigenvalue % |D(1,1)|. D %% w = V(:,1); %% % Finding the Fiedler vector using |eigs| is scalable to larger graphs, % since only a subset of the eigenvalues and eigenvectors are computed, but % for smaller graphs it is equally feasible to convert the Laplacian matrix % to full storage and use |eig(full(L))|. %% Partition Graph % Partition the graph into two subgraphs using the Fiedler vector |w|. A % node is assigned to subgraph A if it has a positive value in |w|. % Otherwise, the node is assigned to subgraph B. This practice is called a % _sign cut_ or _zero threshold cut_. The sign cut minimizes the weight of % the cut, subject to the upper and lower bounds on the weight of any % nontrivial cut of the graph. % % Partition the graph using the sign cut. Highlight the subgraph of nodes % with |w>=0| in red, and the nodes with |w<0| in black. highlight(p,find(w>=0),'NodeColor','r') % subgraph A highlight(p,find(w<0),'NodeColor','k') % subgraph B %% % For the bar bell graph, this partition bisects the graph nicely into two % equal sets of nodes. However, the sign cut does not always produce a % balanced cut. % % It is always possible to bisect a graph by calculating the median of |w| % and using it as a threshold value. This partition is called the _median % cut_, and it guarantees an equal number of nodes in each subgraph. % % You can use the median cut by first shifting the values in |w| by the % median: % % w_med = w - median(w); % % Then, partition the graph by sign in |w_med|. For the bar bell graph, the % median of |w| is close to zero, so the two cuts produce similar % bisections.