CAREER: Stochastic processes and embeddings on networks

Princeton University, Princeton NJ

Investigators

Abstract

Random processes on networks play a major role in a wide range of areas including mathematical physics, machine learning, and theoretical computer science. One such question we will address involves analysing algorithms for detecting sub-communities within a social network by investigating the graph of friendship relations. The proposal addresses questions from combinatorics and computer science about when random combinatorial and computational problems have solutions, such as when there is a colouring in a random graph. Ideas from statistical physics give predictions for these thresholds which we will mathematically prove. It also studies questions of how long it takes random processes on networks, such as the Glauber dynamics Markov chain, to reach their equilibrium distribution and how this depends on their initial starting position. Such processes are used as algorithms for sampling high dimensional distributions. The proposal focuses on development of mathematical theory with a view to better understanding these problems. Finally the proposal will support the development of new graduate courses in discrete probability and stochastic process on random graphs as well as providing research opportunities for graduate and undergraduate researchers. The main theme of this proposal is the development of new theory and applications across a range of stochastic processes on networks. One aspect involves studying phase transitions of Gibbs measures on random graphs, particularly random constraint satisfaction problems. Here we hope to establish conjectures from statistical physics for a range of models such as the chromatic and independence numbers on random graphs. A second theme is the development of new tools for establishing rough isometries and other geometric notions of closeness between random metric spaces. In particular we will consider whether independent copies of Poisson processes, percolation clusters and SLE curves are rough isometries or quasi-symmetries. Finally the proposal will consider Markov random fields such as the Ising model on lattices. At high temperatures it will consider the question of universality of the cutoff phenomena as well as the effect of different initial conditions on the mixing time. At low temperatures it will pursue a better understanding of Ising interfaces in order to establish rapid mixing results.