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.