Far apart: outliers, extremal eigenvalues, and spectral gaps in random graphs and random matrices

在过去的几十年里，科技的进步已经彻底改变了社会运作的方式。大量的数据被产生和收集。这就需要对数据进行分类和分类，以便提取有意义和有用的信息。为了模拟庞大的网络，无论是社会的、生物的还是电子的，数学家和计算机科学家已经引入了图和超图的概念，以及它们的张量、邻接矩阵和谱，并将后者的特性与前者的特性联系起来，以便更好地理解当前技术世界的结构。该项目的目标是促进对随机网络谱中的异常值的基本理解；这些异常值与从机器学习到生物信息学和编码理论的应用有关，因为它们的存在或不存在可以用来推断各种网络特性。该项目的成果可用于开发算法、理论算法保证和各种科学技术应用的基准。通过其教育组成部分（包括研究生和本科生的研究培训机会），该项目将有助于创造并确保下一代数学家和数据科学家的成功。PI将研究具有一定对称性的一般网络模型（例如，齐次和非齐次二部随机图，均匀和非均匀超图，以及超图随机块模型）。项目的一部分涉及创建和分析随机广义特征值算法，该算法基于寻找随机矩阵模型的最小奇异值的紧边界。所采用的方法包括集中技术和非回溯算子，以及来自组合学、概率论、线性代数和统计学的其他技术，以找到在各种图和超图模型中可能存在或不存在异常值的制度的尖锐阈值。PI还将研究超图随机块模型中的社区恢复阈值和检测问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Technological and scientific advances in the last few decades have completely changed the way in which society operates. Massive amounts of data is produced and collected. This creates the need for data to be classified and categorized in order to extract meaningful and useful information. To model enormous networks, whether social, biological, or electrical, mathematicians and computer scientists have introduced the concepts of graphs and hypergraphs, with their tensors, adjacency matrices, and spectra, and have connected properties of the latter to properties of the former in order to better understand the structure of the current technological world. The goal of this project is to advance basic understanding of outliers in the spectra of random networks; such outliers have been connected to applications from Machine Learning to Bioinformatics and Coding Theory, as their presence or absence can be used to deduce various network properties. The results of this project can be used to develop algorithms, theoretical algorithmic guarantees, and benchmarks for a variety of applications in science and technology. Through its educational component (which includes research training opportunities for graduate and undergraduate students), this project will contribute to creating and ensuring the success of the next generation of mathematicians and data scientists. The PI will study general network models with certain symmetry properties (e.g., homogeneous and inhomogeneous bipartite random graphs, uniform and non-uniform hypergraphs, and the Hypergraph Stochastic Block Model). One part of the project involves creating and analyzing a randomized generalized eigenvalue algorithm, based on finding tight bounds on the smallest singular value for a random matrix model. Methods to be employed include concentration techniques and the non-backtracking operator, in addition to other techniques from combinatorics, probability, linear algebra, and statistics, to find sharp thresholds for regimes in which outliers may or may not exist in the variety of graph and hypergraph models. The PI will also study thresholds for community recovery and detection problems in the Hypergraph Stochastic Block Model.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.