Opening Finding Clusters in Graphs
Finding Clusters in Graphs
- Length
- 35 min
- Level
- Undergraduate
- Recorded
- MIT2019
Chapter 1 of 7: Before the lecture
Graph clustering divides a large network into balanced groups of related vertices by finding a good cut. In session 33 of MIT 18.065, Strang first reviews k-means, which alternates between computing cluster centroids and reassigning each node to the nearest one. He then builds spectral clustering on the graph Laplacian, the degree matrix minus the adjacency matrix, and links it to the finite-difference Laplacian on a grid. Its smallest eigenvalue is zero, with the all-ones eigenvector, and the Fiedler vector for the next eigenvalue splits the nodes by sign. The material assumes eigenvalues, symmetric matrices and incidence matrices, and closes with questions on more than two clusters.

Your comment is kept while you sign up.Sign in
Strang splits a graph into two clusters by the signs of the Fiedler vector of its Laplacian, after reviewing k-means.
Graph clustering divides a large network into balanced groups of related vertices by finding a good cut. In session 33 of MIT 18.065, Strang first reviews k-means, which alternates between computing cluster centroids and reassigning each node to the nearest one. He then builds spectral clustering on the graph Laplacian, the degree matrix minus the adjacency matrix, and links it to the finite-difference Laplacian on a grid. Its smallest eigenvalue is zero, with the all-ones eigenvector, and the Fiedler vector for the next eigenvalue splits the nodes by sign. The material assumes eigenvalues, symmetric matrices and incidence matrices, and closes with questions on more than two clusters.
This lecture
Lecture 33 of 34 of Matrix Methods in Data Analysis, Signal Processing, and Machine Learning.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.