Algorithms in Machine Learning: Exercises for Lecture 2, Eigenvalues, Visualisation and Clustering
Question 1. Consider the following undirected, 3-regular graph G with 8 vertices and adjacency matrix
A:
0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0
00101100
1. Compute the Laplacian Matrix L.
A=0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0
2. Compute the second-smallest eigenvalue λ2 and its associated eigenvector x, i.e., Lx = λ2x.
3. Draw the 8 vertices on a line using the values from x as coordinates, and include the edges from the graph G. Can you see a cluster structure? What does it mean if two vertices have the same coordinates, and what does it mean if two vertices have very different coordinates?
Question 2. (see slide 19) What are the eigenvectors with eigenvalue 0 of L in the graph below? Hint: Try to find eigenvectors that reflect the connected components.
145
2376
Question 3. (Bonus) Generalising the example from Question 2), prove that any d-regular with k connected connected components has k orthogonal eigenvectors with eigenvalue 0.
1