Graph Clustering

We revisit the example of social networks from Chapter 1 and deal with the question of how clusters can be found in such a setting. After introducing some terms from graph theory—in particular, the adjacency and Laplace matrix—we explain heuristically how clusters and eigenvalues are linked via the Courant-Fischer formula. After introducing further terms, in particular: normalized Laplace matrix, volume, conductance, we formalize the aforementioned connection via Cheeger’s inequality.