Random walks and graphs, Gibbs measures, dynamics and universality.

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 (weight). Analyzing the data of a specific large network is notoriously challenging. However, for many reasonable models of large random networks one expects the same behavior for most of their likely instances. Furthermore, such limiting behavior is often independent of the detailed definition of the model and governed by an explicit variational formula. This project aims at developing our fundamental understanding of probabilistic modeling by exploring such asymptotic descriptions and gaining both algorithmic and inference insights from them. Graduate and postdoctoral researchers will be mentored and results will be disseminated through newly developed courses and at conferences. 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 will study 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.