SIAM Conference on Applied Linear Algebra (SIAMLA15) mini-symposium on Recent Spectral Approaches for Graph Clustering

October 26, 2015

Talk on joint work with David F. Gleich:

Local Clustering with Graph Diffusions and Spectral Solution Paths

Eigenvectors of graph-related matrices are intimately connected to diffusion processes that model the spread of information across a graph. Local Cheeger inequalities guarantee that localized diffusions like the personalized PageRank eigenvector and heat kernel identify small, good-conductance clusters. We provide constant-time algorithms for computing a generalized class of such diffusions, apply their solution paths to produce refined clusters, and prove that these diffusions always identify clusters of constant size.