Spectra of Large Random Graphs And Applications In Community Detection

我们的社会目前正在产生和收集大量的数据，需要对这些数据进行筛选和有意义的分类，以便做出明智的决策。从社会网络到生物网络，社区检测和聚类问题对于理解网络的本质至关重要；因此，高效可靠的算法对这些问题至关重要。这种算法的设计、分析和基准测试通常严重依赖于随机矩阵和随机图理论，因为研究表明，大型网络特征通常可以通过随机图模型复制（并且更容易研究）。因此，需要有关于大型随机图谱的良好理论结果来理解其典型行为，以及社区检测算法的局限性。PI将研究各种各样的问题，从理论（随机图的光谱）到应用（提出和分析社区检测算法）。考虑的一些模型将包括随机块模型及其变体，特别是在稀疏性的极限下（当平均节点连接要么大而恒定，要么比网络大小的任何次方都慢到无穷大时）。在更理论化的方面，PI将研究从光谱间隙（控制混合等特性，但也可能在某些网络中精确的群落恢复）到经验光谱分布（可用于建立网络的性质）的问题。PI还将研究这些图模型中各种社区检测制度的阈值界限，并将开发用于数值计算各种随机图的渐近谱分布的软件。

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.