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

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

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.