Zoom recording session 1: Remco van der Hofstad, Jean-Stéphane Dhersin.
Zoom recording session 2: Christina Goldschmidt, Nicolas Broutin.
Zoom recording session 3: Lenka Zdeborova, Amin Coja-Oghlan.
Zoom recording session 4: Laurent Massoulié, Pieter Trapman

Nicolas Broutin (Paris), Amin Coja-Oghlan (Frankfurt), Jean-Stéphane Dhersin (Paris), Christina Goldschmidt (Oxford), Laurent Massoulié (Paris), Pieter Trapman (Stockholm), Lenka Zdeborova (Lausanne)

Nicolas Broutin (Paris):The Brownian parabolic tree.

We will discuss the explicit construction of a new random tree from Brownian motion, and relate its distribution to well-known objects related to random graphs and the multiplicative coalescent.

Amin Coja-Oghlan (Frankfurt): Group testing. pdf

In the group testing problem the aim is to identify a small set of infected individuals within a large population. At our disposal we have a test procedure capable of testing groups of several individuals, with the test returning a positive result iff at least one individual in the group is infected. What is the least number of tests that we need to conduct to correctly identify the infected individuals w.h.p., and is there an efficient algorithm for this task?

Jean-Stéphane Dhersin (Paris): Spatial evolution of an epidemic and « social » networks.

One of the criticisms that can be levelled at the modelling of the epidemic is the lack of consideration of spatial structure. A reasonable approach is to plot the epidemic on a graph. We will see what happens on theoretical graphs. However, understanding the true structure of the underlying graph is often complicated. One method is to look at a random branching walk on the graph to find it out. We will look at the information we can get from it. This method, called 'Respondent-driven' study have been applied in Paris to discover the social network of people who inject drugs (PWIDs).

Christina Goldschmidt (Oxford): The scaling limit of a critical random directed graph. pdf

We consider the random directed graph D(n, p) with vertex set {1, 2, . . . , n} in which each of the n(n-1) possible directed edges is present independently with probability p. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at p = 1/n, with critical window p = 1/n + \lambda n^{-4/3} for \lambda \in \R. We show that, within this critical window, the strongly connected components of D(n, p), ranked in decreasing order of size and rescaled by n^{-1/3}, converge in distribution to a sequence of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. This is joint work with Robin Stephenson (Sheffield).

Laurent Massoulié (Paris): Partial alignment of sparse random graphs. pdf

Graph alignment is a generic algorithmic problem with many applications. In this work we consider alignment of sparse random graphs generated from the correlated Erdös-Rényi distribution. We introduce the Neighborhood Tree Matching Algorithm which provably returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds in a challenging regime of graphs with average degree in O(1) and correlation parameter bounded away from 1. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent. This is based on joint work with Luca Ganassali.

Pieter Trapman (Stockholm): Herd immunity, population structure and the second wave of an epidemic.

The classical herd-immunity level is defined as the fraction of a population that has to be immune to an infectious disease in order for a large outbreak of the disease to be impossible, assuming (often implicitly) that the immunized people are a uniform subset of the population.
I will discuss the impact of the immunity level in a population if the immunity is obtained through an outbreak of an infectious disease in a heterogeneous population.
The leading example is a stochastic model for two successive SIR (Susceptible, Infectious, Recovered) epidemic outbreaks or waves in the same population structured by a random network. Individuals infected during the first outbreak are (partially) immune for the second one.
The first outbreak is analysed through a bond percolation model, while the second wave is approximated by a three-type branching process in which the types of individuals depend on their position in the percolation clusters used for the first outbreak. This branching process approximation enables us to calculate a threshold parameter and the probability the second outbreak is large.
This work is based on joined work with Tom Britton and Frank Ball and on ongoing work with Frank Ball, Abid Ali Lashari and David Sirl.

Remco van der Hofstad (Eindhoven): Critical percolation on scale-free random graphs. pdf

Empirical findings have shown that many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Spurred by these empirical findings, models have been proposed for such networks.
Percolation on networks is one of the simplest models for network functionality. It can be interpreted as describing the effect of random attacks on the network, where edges are removed independently with a fixed probability, or the result of an epidemic on the network. Interestingly, networks with diverging second moment degree tend to be robust to such random attacks, in the sense that a giant component remains after percolation for any fixed positive retention probability. For an epidemic, this means that it will be pandemic even for very small transmission probabilities.
We investigate the critical behavior for two popular models of complex networks with diverging second moments, the configuration model and the generalized random graph or hidden-variable model. We identify what the critical values are, and how they scale with the graph size. Interestingly, this scaling turns out to be rather different for the configuration model, where hubs share many edges between them, and the generalized random graph, for which hubs are connected by at most one edge. Thus, the single-edge constraint plays a significant role. This clears up part of the confusion in the physics literature.
This is joint work with Shankar Bhamidi, Souvik Dhara, Johan van Leeuwaarden and Sanchayan Sen.
Aside from this, I will give a brief introduction to the day on "Structure and function of complex networks: epidemics and optimization".

Lenka Zdeborova (Lausanne): Epidemic mitigation by statistical inference from contact tracing data. pdf

Contact tracing mobile applications are clear candidates enabling us to slow down an epidemics and keep the society running while holding the health risks down. Most of the currently discussed and developed mobile applications aim to notify individuals who were recently in a significant contact with an individual who tested positive. The contacted individuals would then be tested or/and put in isolation. In our work, we aim to quantify the epidemiological gain one would obtain if, additionally, individuals who were recently in contact could exchange messages of information. With such a message passing the risk of contracting the infection could be estimated with much better accuracy than simple contact tracing. Our results show that in some range of epidemic spreading (typically when the manual tracing of all contacts of infected people becomes practically impossible, but before the fraction of infected people reaches the scale where a lock-down becomes unavoidable), this inference of individuals at risk could be an efficient way to mitigate the epidemic. Our approaches translate into fully distributed algorithms that only require communication between individuals who have recently been in contact. We conclude that probabilistic risk estimation is capable of enhancing the performance of digital contact tracing and should be considered in the currently developed mobile applications. Based on: https://arxiv.org/abs/2009.09422
=======

Zoom recording session 1: Remco van der Hofstad, Jean-Stéphane Dhersin.
Zoom recording session 2: Christina Goldschmidt, Nicolas Broutin.
Zoom recording session 3: Lenka Zdeborova, Amin Coja-Oghlan.
Zoom recording session 4: Laurent Massoulié, Pieter Trapman

Nicolas Broutin (Paris), Amin Coja-Oghlan (Frankfurt), Jean-Stéphane Dhersin (Paris), Christina Goldschmidt (Oxford), Laurent Massoulié (Paris), Pieter Trapman (Stockholm), Lenka Zdeborova (Lausanne)

Nicolas Broutin (Paris):The Brownian parabolic tree.

We will discuss the explicit construction of a new random tree from Brownian motion, and relate its distribution to well-known objects related to random graphs and the multiplicative coalescent.

Amin Coja-Oghlan (Frankfurt): Group testing. pdf

In the group testing problem the aim is to identify a small set of infected individuals within a large population. At our disposal we have a test procedure capable of testing groups of several individuals, with the test returning a positive result iff at least one individual in the group is infected. What is the least number of tests that we need to conduct to correctly identify the infected individuals w.h.p., and is there an efficient algorithm for this task?

Jean-Stéphane Dhersin (Paris): Spatial evolution of an epidemic and « social » networks.

One of the criticisms that can be levelled at the modelling of the epidemic is the lack of consideration of spatial structure. A reasonable approach is to plot the epidemic on a graph. We will see what happens on theoretical graphs. However, understanding the true structure of the underlying graph is often complicated. One method is to look at a random branching walk on the graph to find it out. We will look at the information we can get from it. This method, called 'Respondent-driven' study have been applied in Paris to discover the social network of people who inject drugs (PWIDs).

Christina Goldschmidt (Oxford): The scaling limit of a critical random directed graph. pdf

We consider the random directed graph D(n, p) with vertex set {1, 2, . . . , n} in which each of the n(n-1) possible directed edges is present independently with probability p. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at p = 1/n, with critical window p = 1/n + \lambda n^{-4/3} for \lambda \in \R. We show that, within this critical window, the strongly connected components of D(n, p), ranked in decreasing order of size and rescaled by n^{-1/3}, converge in distribution to a sequence of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. This is joint work with Robin Stephenson (Sheffield).

Laurent Massoulié (Paris): Partial alignment of sparse random graphs. pdf

Graph alignment is a generic algorithmic problem with many applications. In this work we consider alignment of sparse random graphs generated from the correlated Erdös-Rényi distribution. We introduce the Neighborhood Tree Matching Algorithm which provably returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds in a challenging regime of graphs with average degree in O(1) and correlation parameter bounded away from 1. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees. These results may be of independent interest, yielding for instance efficient tests for determining whether two random trees are correlated or independent. This is based on joint work with Luca Ganassali.

Pieter Trapman (Stockholm): Herd immunity, population structure and the second wave of an epidemic.

The classical herd-immunity level is defined as the fraction of a population that has to be immune to an infectious disease in order for a large outbreak of the disease to be impossible, assuming (often implicitly) that the immunized people are a uniform subset of the population.
I will discuss the impact of the immunity level in a population if the immunity is obtained through an outbreak of an infectious disease in a heterogeneous population.
The leading example is a stochastic model for two successive SIR (Susceptible, Infectious, Recovered) epidemic outbreaks or waves in the same population structured by a random network. Individuals infected during the first outbreak are (partially) immune for the second one.
The first outbreak is analysed through a bond percolation model, while the second wave is approximated by a three-type branching process in which the types of individuals depend on their position in the percolation clusters used for the first outbreak. This branching process approximation enables us to calculate a threshold parameter and the probability the second outbreak is large.
This work is based on joined work with Tom Britton and Frank Ball and on ongoing work with Frank Ball, Abid Ali Lashari and David Sirl.

Remco van der Hofstad (Eindhoven): Critical percolation on scale-free random graphs. pdf

Empirical findings have shown that many real-world networks are scale-free in the sense that there is a high variability in the number of connections of the elements of the networks. Spurred by these empirical findings, models have been proposed for such networks.
Percolation on networks is one of the simplest models for network functionality. It can be interpreted as describing the effect of random attacks on the network, where edges are removed independently with a fixed probability, or the result of an epidemic on the network. Interestingly, networks with diverging second moment degree tend to be robust to such random attacks, in the sense that a giant component remains after percolation for any fixed positive retention probability. For an epidemic, this means that it will be pandemic even for very small transmission probabilities.
We investigate the critical behavior for two popular models of complex networks with diverging second moments, the configuration model and the generalized random graph or hidden-variable model. We identify what the critical values are, and how they scale with the graph size. Interestingly, this scaling turns out to be rather different for the configuration model, where hubs share many edges between them, and the generalized random graph, for which hubs are connected by at most one edge. Thus, the single-edge constraint plays a significant role. This clears up part of the confusion in the physics literature.
This is joint work with Shankar Bhamidi, Souvik Dhara, Johan van Leeuwaarden and Sanchayan Sen.
Aside from this, I will give a brief introduction to the day on "Structure and function of complex networks: epidemics and optimization".

Lenka Zdeborova (Lausanne): Epidemic mitigation by statistical inference from contact tracing data. pdf

Contact tracing mobile applications are clear candidates enabling us to slow down an epidemics and keep the society running while holding the health risks down. Most of the currently discussed and developed mobile applications aim to notify individuals who were recently in a significant contact with an individual who tested positive. The contacted individuals would then be tested or/and put in isolation. In our work, we aim to quantify the epidemiological gain one would obtain if, additionally, individuals who were recently in contact could exchange messages of information. With such a message passing the risk of contracting the infection could be estimated with much better accuracy than simple contact tracing. Our results show that in some range of epidemic spreading (typically when the manual tracing of all contacts of infected people becomes practically impossible, but before the fraction of infected people reaches the scale where a lock-down becomes unavoidable), this inference of individuals at risk could be an efficient way to mitigate the epidemic. Our approaches translate into fully distributed algorithms that only require communication between individuals who have recently been in contact. We conclude that probabilistic risk estimation is capable of enhancing the performance of digital contact tracing and should be considered in the currently developed mobile applications. Based on: https://arxiv.org/abs/2009.09422