%% Simple spectral graph partitioning in Matlab
%
% last edited: 2011 October 25
%
% author: David Gleich

%% Setup some functions
% We'll need a few helper functions that we'll quickly define here.
laplacian = @(A) diag(sum(A,2)) - A;

%% Finding a partition
% In this segment, we'll plant a partition in a graph,
% and then use the second smallest eigenvector to find it.
%
% As always, the first step is to generate our dataset. 
% In this example, we'll be a little more ambitious and 
% use a larger number of vertices. 

n = 1000;

%%
% To plant an artificial partition in our dataset, we 
% need to determine the vectices in each of the groups.
% To do this, we randomly generate a permutation of all
% the vertices and select one set as group 1 and the 
% rest as group 2. The variable gs controls how big the
% size of the first group.

x = randperm(n);
gs = 450;
group1 = x(1:gs);
group2 = x(gs+1:end);

%%
% Now, we need to decide on the probabilities of edges
% within each group and between the two groups. Because 
% we are planting a partition, the probabilities of edges
% between the groups should be much lower than the 
% probability of edges within each group. Suppose that 
% group 1 is a little more tightly connected than group 2.
% (Please insert your own amusing names for an actual 
% identification of group 1 and group 2, e.g. politicians
% and mathematicians.)

p_group1 = 0.5;
p_group2 = 0.4;
p_between = 0.1;

%%
% With these probabilities in hand, we can construct our 
% graph. The last few operations symmetrize the matrix.

A(group1, group1) = rand(gs,gs) < p_group1;
A(group2, group2) = rand(n-gs,n-gs) < p_group2;
A(group1, group2) = rand(gs, n-gs) < p_between;
A = triu(A,1);
A = A + A';

%%
% Next, let's see if we can see the partition.

spy(A);

%%
% While some might claim to see a partition in this data, 
% I think it is not particularly obvious.
%
% Now, let's investigate what the second smallest eigenvector
% tells us about this graph.

L = laplacian(double(A));
[V D] = eigs(L, 2, 'SA');
D(2,2)

%%
% The large second smallest eigenvalue states 
% that we shouldn't expect to find any very good
% cuts in our dataset. To see what we found, let's
% plot the second smallest eigenvector V(:,2).

plot(V(:,2), '.-'); 

%%
% That isn't all that helpful. Maybe sorting the vector...

plot(sort(V(:,2)), '.-'); 

%%
% Now, that picture is much more informative! 
% We see a large gap in the middle of the values.
% Interestingly enough, the number of points on 
% the right gap is the same as gs, the size of 
% our planted group. Let's see what happens when
% we permute the vertices of the graph to this ordering.

[ignore p] = sort(V(:,2));
spy(A(p,p)); 

