Spectral Clustering

   2 ----6
 /  \    |
1    4   |
 \  /  \ |
  3      5 


The goal is to find two clusters in this graph using Spectral Clustering on the Laplacian matrix. Compute the Laplacian of this graph. Then compute the second eigen vector of the Laplacian (the one corresponding to the second smallest eigenvalue).

A = matrix(c(0,1,1,0,0,0,
			 1,0,0,1,0,1,
			 1,0,0,1,0,0,
			 0,1,1,0,1,0,
			 0,0,0,1,0,1,
			 0,1,0,0,1,0),nrow=6,ncol=6,byrow=TRUE)
colnames(A) <- c("1","2","3","4","5","6")
rownames(A) <- c("1","2","3","4","5","6")

B = matrix(c(2,0,0,0,0,0,
			 0,3,0,0,0,0,
			 0,0,2,0,0,0,
			 0,0,0,3,0,0,
			 0,0,0,0,2,0,
			 0,0,0,0,0,2),nrow=6,ncol=6,byrow=TRUE)
L = B - A
print(L)
e <- eigen(L)

R can be used to get the eigen values and vectors. But Wolfram gives these values.

Eigenvalues

\lambda1 = 5\\  \lambda2 = 3\\  \lambda3 = 3\\  \lambda4 = 2\\  \lambda5 = 1\\  \lambda6 = 0\\

Eigenvectors

\begin{pmatrix}  1& -2& -1& 2& -1& 1\\  0& -1& 1& -1& 0& 1\\  1& -1& 0& -1& 1& 0\\  1& 1& -1& -1& -1& 1\\  -1& 0& -1& 0& 1& 1\\  1& 1& 1& 1& 1& 1\\  \end{pmatrix}

The second highest eigen value is \lambda5 = 1\\

So the 5th row of the eigen vector matrix is

\begin{pmatrix}  -1& 0& -1& 0& 1& 1\\  \end{pmatrix}

This means that the
1st and 3rd nodes are part of one cluster and 5th and 6th nodes are part of the other cluster. 2nd and 3rd nodes can be part of either cluster.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: