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

过去几十年来，技术和科学的进步彻底改变了社会运作的方式。 产生并收集大量数据。这就需要对数据进行分类和分类，以便提取有意义和有用的信息。为了对巨大的网络（无论是社会网络、生物网络还是电气网络）进行建模，数学家和计算机科学家引入了图和超图的概念及其张量、邻接矩阵和谱，并将后者的属性与前者的属性联系起来，以便更好地理解当前技术世界的结构。该项目的目标是增进对随机网络谱中异常值的基本理解；此类异常值已与机器学习、生物信息学和编码理论等应用相关联，因为它们的存在或不存在可用于推断各种网络属性。该项目的成果可用于开发算法、理论算法保证以及各种科学技术应用的基准。通过其教育部分（包括为研究生和本科生提供研究培训机会），该项目将有助于培养并确保下一代数学家和数据科学家的成功。 PI 将研究具有某些对称特性的通用网络模型（例如，同质和非齐次二分随机图、均匀和非均匀超图以及超图随机块模型）。该项目的一部分涉及创建和分析一种随机广义特征值算法，该算法基于寻找随机矩阵模型的最小奇异值的严格界限。要采用的方法包括集中技术和非回溯算子，以及来自组合学、概率、线性代数和统计学的其他技术，以找到各种图和超图模型中可能存在也可能不存在异常值的状态的尖锐阈值。 PI 还将研究超图随机块模型中社区恢复和检测问题的阈值。该奖项反映了 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.