Spectra of Large Random Graphs And Applications In Community Detection

University Of Washington, Seattle WA

Investigators

Abstract

Our society is currently producing and collecting tremendous amounts of data, which needs to be sifted through and categorized meaningfully in order to lead to informed decision-making. From social networks to biological ones, the problems of community detection and clustering are paramount to understanding the nature of the network; as such, efficient and reliable algorithms for these problems are of utmost importance. Devising, analyzing, and benchmarking such algorithms often rely heavily on random matrix and random graph theory, as studies have shown that large network characteristics can often be replicated (and more easily studied) via random graph models. Thus, good theoretical results on the spectra of large random graphs are needed to understand the typical behavior, as well as the limitations of community detection algorithms. The PI will work on a variety of problems, ranging from the theoretical (spectral of random graphs) to the applied (proposing and analyzing community detection algorithms). Some of the models considered will include the Stochastic Block Model and variants thereof, especially at the limit of sparseness (when average node connectivity is either large and constant or goes to infinity slower than any power of the network size). On the more theoretical side, the PI will work on problems from spectral gap (which controls properties like mixing, but also the possibility of exact community recovery in certain networks) to the empirical spectral distribution (which can be used to establish the nature of the network). The PI will also work on threshold bounds for various regimes of community detection in these graph models, and will produce software for numerically computing the asymptotical spectral distributions for a large variety of random graphs.