NETWORKS

Day 1 (April 6) @ 13:30–15:00

Shankar Bhamidi (University of North Carolina)

David Aldous and the mathematics of networks

The aim of this talk is to describe a personal view of the impact of David Aldous (the 2020 recipient of the Brouwer award) in the world of networks through the following three settings:

a) Mathematical foundations of exponential random graphs: one of the most well used models of networks especially in areas such as sociology, political science and epidemiology are the so called exponential random graph models. I will describe how Aldous’s fundamental contributions in understanding mixing time of Markov Chains leads to an understanding of MCMC algorithms to sample from this distribution. If there is time, I will also describe how the Aldous-Hoover theory of exchangeability is fundamental in understanding the large network asymptotics of these models as proven by Chatterjee and Diaconis. 

b) First passage percolation,  Preferential attachment models and branching process: I will describe the impact of Aldous’s work (a by-product of trying to understand local weak convergence of random tree models) in elucidating connections between fundamental results on continuous time branching processes laid by Athreya-Ney and Jagers-Nerman and structural properties of network models such as preferential attachment models and understanding information diffusion models such as first passage percolation. 

c) Strong disorder models and the minimal spanning tree: We will finally end with how Aldous’s work in understanding coagulation models in statistical physics turned out to be one of the fundamental ingredient in understanding the behavior of objects such as the minimal spanning tree on network models with iid edge weights. 

Much of this work is with many collaborators. I will intersperse the talk with advice given to me by David at various crucial times in my career.

Pieter Kleer (Max-Planck-Institut für Informatik)

The switch Markov chain for sampling graphs with given degrees

The uniform sampling (or generation) of graphs with given degrees is an important problem in the analysis of complex networks. One of the simplest approaches to this problem is the switch Markov chain. Given some starting graph, one repeatedly switches two edges uniformly at random, while preserving the degree sequence. How many switches are needed before the resulting network is close to a uniform sample from the set of all graphs with the given degrees? The answer to this question is still open for general degree sequences. 

In this talk we will sketch a novel proof approach for the analysis of the switch Markov chain, based on Sinclair’s multi-commodity flow method. The analysis relies on combinatorial arguments (no knowledge of Markov chains is required beyond the basic definition). In particular, our proof approach allows us to extend the existing range of degree sequences for which the switch Markov chain is known to be rapidly mixing (the chain is called rapidly mixing if only a polynomial number of switches is needed to get close to a uniform sample). If time permits, we will also discuss some extensions of the problem.

Based on joint work with Georgios Amanatidis.