Asymptotics in Probability: Walks and Graphs, Disordered Measures, and Dynamics

网络和图是描述真实世界系统(社会网络、交通网络、生物系统等)的普遍数学模型。网络由一定数量的对象(称为节点)组成，这些对象通过各种重要性(权重)的链路相连。分析特定大型网络的数据是出了名的挑战，但对于许多合理的大型随机网络模型，至少对于大多数可能的网络实例，人们都有有效的算法来解决此类问题。这个项目的目的是发展我们对这种概率模型的基本理解，从而为它们推导出某些类型的有效算法。该项目为研究生提供了研究培训机会。该项目专注于稀疏随机图的各种模型，最简单的是鄂尔多斯-仁义(独立边)随机图，具有缓慢增长的或有界的平均度。许多统计推理任务可以通过适当定义的组合优化问题来解决，这些问题的解可以从基础图上适当的Gibbs度量的基态恢复。这个项目旨在研究大型随机图的各种渐近性质以及它们上的自然随机演化，从而了解它们不变的Gibbs度量的潜在丰富结构。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Networks and graphs are ubiquitous mathematical models to describe real world systems (social networks, transportation networks, biological systems, and so on). A network comprises a certain number of objects (referred to as nodes) connected by links of various importance (weights). Analyzing the data of a specific large network is notoriously challenging, but for many reasonable models of large random networks one has efficient algorithms to solve such problems, at least for most of the network likely instances. This project aims at developing our fundamental understanding of such probabilistic models and thereby deriving certain classes of efficient algorithms for them. The project provides research training opportunities for graduate students. The project focuses on various models of sparse random graphs, the simplest being the Erdos-Renyi (independent edges) random graph, with slowly growing, or bounded, average degree. Many statistical inference tasks can be addressed by suitably defined combinatorial optimization problems whose solutions can be recovered from the ground states of suitable Gibbs measures on the underlying graph. This project aims at studying various asymptotic properties of large random graphs as well as natural stochastic evolutions on them, thus gaining understanding of the underlying rich structure of the Gibbs measures for which they are invariant.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.