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

Stanford University, Stanford CA

Investigators

Abstract

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.