# Spectral graph partitioning in Haskell

I was reading some notes from QUT about using spectral graph theory to partition a graph using eigenvalues of unnormalised Laplacian. Their Matlab code looks like this:

```
% Form W = Gaussian distribution based on distances
W = zeros(100, 100);
D = zeros(100, 100);
sigma = 2;
N = 100;
for i = 1:N
for j = 1:N
if (j ~= i)
% Calculate the distance between two points
dist = norm([A(i, 1) - A(j, 1); A(i, 2) - A(j, 2)]);
expp = exp(-dist^2 / (2 * sigma^2));
adjacency(i, j) = 1;
% Add the weights to the matrix
W(i, j) = expp;
% Add up the row sum as we go
D(i, i) = D(i, i) + expp;
end
end
end
L = D - W;
Find the eigenpairs of L
[vec, val] = eig(L, 'vector');
% Ensure the eigenvalues and eigenvectors are sorted in ascending order
[val,ind] = sort(val);
vec = vec(:, ind);
% Plot with clusters identified by marker
% v2
figure;
hold on;
for i = 1:N
plot(i, vec(i, 2), ['k' plot_syms{i}]);
end
```

Personally, this gives me nightmares from undergrad numerical methods classes. So here’s how to do it in Haskell. Full source (including cabal config) for this post is here.

To create the `W`

matrix we use `buildMatrix`

:

The `D`

matrix is a diagonal matrix with each element
being the sum of a row of `W`

, which is nicely expressible
by composing a few functions:

The `L`

matrix is real and symmetric so we
use eigSH which provides the eigenvalues in descending order.

To finish up, the Fiedler eigenvector corresponds to the second smallest eigenvalue:

To plot the eigenvalues and eigenvector we use the Chart library which uses the cairo backend.