CIF: Small: Projective limits of sparse graphs

对许多极其重要的社会现象的预测和控制，如战争和流行病，需要处理大量的关系数据。这些关系数据通常采用网络或图表的形式。为了便于分析这些巨大的图形，人们通常假设它们的大小是无限的。然而，这种假设往往忽略了一个关键点，即这些限制可能定义不清，或者根本不存在，因为现实世界的网络是稀疏的--连接相对较少--但稀疏图形限制的理论仍然知之甚少，几乎不存在。因此，基于其无限大小的理想化来得出关于现实世界中的稀疏网络的结论可能非常具有误导性。这个项目试图通过开发一种新的稀疏图形极限理论的方法来解决这个问题，这种方法被称为“石墨化物”。如果成功，该项目将在神经科学、图嵌入、机器学习和电信网络中的路由等领域的应用中带来严格的预测保证。Graphide在概念上类似于“Graphons”--密集图的极限--因为它们本质上是带有潜在变量的随机图模型中的连接概率函数。然而，与石墨子不同的是，石墨化物定义在无限体积的潜在空间中，以实现图形稀疏。用来证明稀疏图收敛到石墨线的主要方法植根于射影极限理论，这是Kolmogorov扩张定理的推广，它将随机过程的存在条件建立为一族有限维分布的极限。该项目的首要目标是确定以石墨化物为极限的稀疏随机图模型的类别。为了实现这一点，子目标包括一般射影图极限方法的技术开发及其在石墨层、石墨层和石墨层上的应用。通过将这种方法应用于一系列潜在空间模型，包括随机双曲线图--在研究人员之前由NSF资助的研究中开发的一种非常有影响力的现实世界网络模型--该项目旨在证明这些模型以石墨化物为极限并识别这些石墨化物。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The prediction and control of many phenomena of utmost societal importance, such as wars and pandemics, deal with massive volumes of relational data. These relational data often take the form of networks or graphs. To make the analysis of these massive graphs tractable, one typically assumes that their size is infinite. However, this assumption often overlooks a crucial point that these limits may be ill-defined or simply non-existent because real-world networks are sparse -- having relatively few connections -- but the theory of sparse graph limits remains poorly understood, next to non-existent. Therefore, drawing conclusions about real-world sparse networks based on their infinite-size idealizations can be quite misleading. This project seeks to address this problem by developing a novel approach to the theory of sparse graph limits, an approach called "graphides." If successful, this project will lead to rigorous prediction guarantees in applications spanning areas such as neuroscience, graph embedding, machine learning, and routing in telecommunication networks. Graphides are conceptually similar to "graphons" -- limits of dense graphs -- in that they are essentially the connection probability functions in random graph models with latent variables. Unlike graphons, however, graphides are defined within latent spaces of infinite volume to achieve graph sparsity. The primary methods used to demonstrate the convergence of sparse graphs to graphides are rooted in the theory of projective limits, a generalization of the Kolmogorov extension theorem that establishes the conditions for the existence of a stochastic process as the limit of a family of finite-dimensional distributions. The overarching objective of the project is to identify categories of sparse random graph models that have graphides as their limits. To achieve this, sub-goals include the technical development of the general projective graph limit methodology and its application to graphons, graphexes, and graphides. By applying this methodology to a collection of latent-space models, including random hyperbolic graphs -- a highly influential model of real-world networks developed in the investigator's previous NSF-funded research -- the project aims to demonstrate that these models have graphides as their limits and identify these graphides.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.