Random walks on graphs and hypergraphs: eigenvalues and clustering

 In this two-part talk, we discuss several combinatorics problems rooted in the study of random walks. In the first half, we discuss problems in extremal spectral graph theory pertaining to random walk parameters. Focusing first on undirected graphs, we find the minimum spectral gap of the normalized Laplacian matrix over all simple, connected n-vertex graphs, settling a conjecture of Aldous and Fill. Turning attention to directed graphs, we then consider the principal ratio, a measure of digraph irregularity based on the maximum to minimum values of vertices in the stationary distribution. We also discuss the directed analog of the normalized Laplacian matrix, and prove a lower bound on its spectral gap.
        In the second half, we propose a Laplacian based approach for clustering hypergraph-structured data. Our proposed method is rooted in recent work, which has advocated utilizing edge-dependent vertex weights to define non-reversible hypergraph random walks. Based on these, we employ tools developed in the first half of the talk to construct hypergraph Laplacians and design clustering algorithms that utilize them as inputs. Testing on real data, we compare the performance of these clustering algorithms experimentally against a variety of existing hypergraph clustering methods.