CIF: Small: Projective limits of sparse graphs

CIF：小：稀疏图的投影极限

• 批准号: 2311160
• 负责人: Dmitri Krioukov
• 金额: $ 30万
• 依托单位: Northeastern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-12-01 至 2026-11-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2311160&HistoricalAwards=false
• 关键词: CIF; Small; Projective; limits; sparse

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.

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