Graph Clustering Algorithms

October 10, 2017

On September 28, 2017, Tselil Schramm (Simons Institute, UC Berkeley) spoke about graph clustering algorithms (video, slides). This was the first talk in our new Graphs across Domains (GraphXD) monthly seminar series. Next week (Thursday, October 19th), Nikhil Srivastava (Department of Mathematics, UC Berkeley will speak about the spectral sparsification of graphs.

Both speakers use the Laplacian matrix representation for undirected graphs. Since this matrix is symmetric about its diagonal, the spectral theorem tells us that it has the following useful decomposition:

Spectral Theorem. Let \(A\) be a symmetric (i.e, \(A=A^\top\)), real-valued \(n \times n\) matrix. Then \(A\) can be decomposed as \[ A = Q \Lambda Q^\top \] where \(Q\) is an orthogonal matrix (i.e., \(Q^\top Q = I\)) and \(\Lambda\) is a diagonal matrix containing the \(n\) (not necessarily distinct) real eigenvalues of \(A\).

The \(n\) eigenvalues are called the spectrum of the Laplacian matrix, which has many useful properties and applications.

If you are interested in reviewing this material you may enjoy Gilbert Strang’s lectures on eigenvalues and eigenvectors and symmetric matrices and positive definiteness. You may also enjoy his lecture on graphs, networks, and incidence matrices.

Sign up for the GraphXD announcement list here.