Schedule: 11 May 2021, 14:00 GMT/16:00 Italian time

Virtual link: https://us02web.zoom.us/j/83390778311

Speaker: Andrea Clementi (Università di Roma “Tor Vergata”)

TITLE: Sharp Thresholds for a SIR Model on One-Dimensional Small-World Networks

ABSTRACT: After a short overview of the basic notions of the classic Susceptible-Infectious-Recovered (SIR) epidemic model in the fully-mixed scenario, we review some fundamental results of the discrete-time version of the SIR model, known as Reed-Frost model, in some simple network topologies. We then consider the the Reed-Frost model over “small-world” graphs, in which graphs are obtained by adding random edges to a cycle. In 3-regular graphs obtained as the union of a cycle and a random perfect matching, we show that there is a sharp threshold at 0.5 for the contagion probability along edges. In graphs obtained as the union of a cycle and of an Erdos-Renyi random graph with n nodes and edge probability c/n, we show that there is a sharp threshold p_c for the contagion probability: the value of p_c turns out to be about 0.41 for the sparse case c=1 yielding an expected node degree similar to the random 3-regular graphs above. In both models, below the threshold we prove that the infection only affects O(log n) nodes, and that above the threshold it affects Omega(n) nodes. These are the first fully rigorous results establishing a phase transition for SIR models (and equivalent percolation problems) in small-world graphs. Although one-dimensional small-world graphs are an idealized and unrealistic network model, a number of realistic qualitative phenomena emerge from our analysis, including the spread of the disease through a sequence of local outbreaks, the danger posed by random connections, and the effect of super-spreader events. This is a joint research with Luca Becchetti, Riccardo Denni, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi.

BIO:  Andrea Clementi is Professor of Computer Science at the University of Rome “Tor Vergata”. He graduated with honors in Mathematics and got the PhD in Computer Science at Sapienza University of Rome. He was a researcher at Sapienza University of Rome and at the University of Geneva. He is now teaching the courses “Algorithms and Data Structures” and “Distributed Algorithms and Complex Networks” in the Degree Program in Computer Science of the University of Rome “Tor Vergata”. He is currently a member of the Doctoral College in Engineering and Information Sciences of the University of L’Aquila. His current scientific interests are in algorithm theory and applied probability, in particular, in the modeling and analysis of stochastic processes of distributed systems. He has published more than ninety articles in major international journals and conference proceedings.