Graph Limits and Measurable Graphs

图限制和可测量图

基本信息

批准号：
1800738
负责人：
Gabor Lippner
金额：
$ 15万
依托单位：
Northeastern University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-07-01 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1800738&HistoricalAwards=false
关键词：
Graph Limits Measurable Graphs

项目摘要

Understanding the structure and properties of large real-life networks has become one of the most important scientific challenges of our time. Large networks are ubiquitous in both the natural and social sciences and we have access to more-and-more data about them. However, most existing methods for analyzing this data are too slow for even moderately large networks. Hence the need to devise, new, robust tools for network analysis. One way of building new tools is to advance our understanding of the underlying structure of large networks. This approach has led to tremendous success in the case of networks with relatively many connections (so called dense networks). However, most real-word networks do not fall into this category (they are so-called sparse), and our understanding of their structural properties remain rather limited. The goal of this project is to advance the understanding of large sparse networks through the study of similarities between networks, and via the use of continuous models - so called graph limits - to approximate large networks. This approach has proved extremely successful in the case of dense networks. Progress in the sparse case has been slow mainly because the "right" notion of similarity seems elusive, and a host of different concepts have emerged over time whose relationship to each other remains unclear. The project will focus on the graph limits, networks defined on probability measure spaces, so-called graphings. It will investigate classical graph theoretic notions on such objects. The few known results indicate that graphings frequently exhibit surprising differences compared to classical graphs. Yet, one can often find natural assumptions under which classical results extend to the measurable context without any change. The central motivating question of the project is the approximability of graphings by finite graphs. To this end, various combinatorial and algebraic properties of graphings will be explored in detail to allow comparison to finite graphs. The combinatorial aspects include understanding how standard theorems in graph theory about the existence of matchings, vertex- and edge-colorings generalize to graphings. Algebraic aspects include the study of spectral properties of graphings.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.

了解大型现实网络的结构和属性已成为我们这个时代最重要的科学挑战之一。大型网络在自然科学和社会科学中无处不在，我们可以获得越来越多的有关它们的数据。然而，即使对于中等规模的网络来说，大多数用于分析这些数据的现有方法也太慢。因此需要设计新的、强大的网络分析工具。构建新工具的一种方法是加深我们对大型网络底层结构的理解。这种方法在具有相对较多连接的网络（所谓的密集网络）的情况下取得了巨大的成功。然而，大多数真实世界的网络并不属于这一类（它们是所谓的稀疏网络），并且我们对其结构特性的理解仍然相当有限。该项目的目标是通过研究网络之间的相似性，并通过使用连续模型（所谓的图极限）来近似大型网络，以增进对大型稀疏网络的理解。事实证明，这种方法在密集网络的情况下非常成功。稀疏案例的进展缓慢，主要是因为“正确”的相似性概念似乎难以捉摸，并且随着时间的推移出现了许多不同的概念，它们之间的关系仍不清楚。该项目将重点关注图形限制，即在概率测度空间上定义的网络，即所谓的图形。它将研究此类对象的经典图论概念。少数已知结果表明，与经典图表相比，图表经常表现出令人惊讶的差异。然而，人们经常可以找到自然假设，在这些假设下，经典结果可以不加任何改变地延伸到可测量的环境。该项目的核心问题是有限图的图形逼近性。为此，将详细探讨图形的各种组合和代数属性，以便与有限图进行比较。组合方面包括理解图论中关于匹配、顶点和边着色的存在的标准定理如何推广到图形。代数方面包括图形光谱特性的研究。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（3）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Ollivier-Ricci curvature convergence in random geometric graphs

随机几何图中的 Olivier-Ricci 曲率收敛

DOI：
10.1103/physrevresearch.3.013211
发表时间：
2021-03
期刊：
Physical Review Research
影响因子：
4.2
作者：
van der Hoorn, Pim;Cunningham, William J.;Lippner, Gabor;Trugenberger, Carlo;Krioukov, Dmitri
通讯作者：
Krioukov, Dmitri

Regular Graphs with Many Triangles are Structured

具有许多三角形的正则图是结构化的