Networks

NETWORKS

Day 2 (April 15) @ 11:00 – 12:30

Shankar Bhamidi
(University of North Carolina)

Title: Dynamic networks and universality for critical random graphs

Over the last few years a wide array of random graph models have been postulated. Most of these models come with a parameter $t$ (usually related to edge density) and a (model dependent) critical time $t_c$ which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős–Rényi random graph, in the sense that (a) sizes of maximal components in the critical scaling window scale like $n^{2/3}$ and (b) the structure of components in this window (rescaled by $n^{−1/3}$) converge to random fractals. Till date, (a) has been proven for a number of models using different techniques while (b) has been proven for the classical Erdős–Rényi random graph. The main aim of this talk is to describe general techniques to prove this program leveraging a host of sophisticated probabilistic techniques developed by Aldous in the 90s in a series of ground breaking papers.

Based on joint work with Nicolas Broutin, Souvik Dhara, Remco van der Hofstad, Sanchayan Sen and Xuan Wang

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

Title: 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.