Rigorous analysis of stochastic network infection processes

Master Project - Summer 2021

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Andreas Göbel, Marcus Pappik
Link: Master Projects IT System Engineering

Motivation

Understanding the spread of infections in populations is crucial for predicting their behavior and counteracting epidemics. However, empirical observations across several outbreaks are usually hard to obtain and real world experiments are not viable. Therefore, mathematical models of epidemics are of central importance for studying the behavior of infections. Not only they allow for simulations, but also give rise to rigorous results about the impact of different parameters of an infection process.

Driven by an improved understanding of properties of real world networks, models which allow for structured populations became more popular within recent decades. To this end, a population is modeled by an undirected graph. Vertices of the graph represent individuals (people, computer in a network, ...) which, depending on the model in question, can have different states, such as susceptible, infected or recovered (immune). Further, edges in the graph serve as potential contacts between individuals, along which the infection can spread from an infected vertex to a susceptible neighbor.

Progression of flu contagion in the friendship network over time. Infected individuals (vertices) are colored red, friends (neighbors) of infected individuals are yellow. The size of each vertex represents the number of infected friends [1].

Typical questions that can be asked for such models are:

How long does the infection survive on the network?
How many and which vertices get infected?
What is the typical path that an infection takes to traverse the network?
How does the structure of the underlying graph affect the process?
Can we alter the structure of the graph so that the infection dies out quickly (see e.g. [2])?

To account for the uncertainty, that usually arises when it comes to epidemics in real world scenarios, the healing of vertices and the transmission of the infection via edges are often represented in terms of probability distributions over time. As a result, the above questions can be answered based on the expected behavior of the process and the outcomes that occur with high probability.

The purpose of this project

We aim for studying variants of stochastic infection processes on networks. This especially includes rigorous mathematical results, for example on (but not limited to) the questions above. To prove such theoretical statements, extensive simulations will be helpful for gaining intuition and deciding the course of action.

What we expect from you

We expect a basic understanding of graph-theoretic concepts and a general interest in probability theory. You should bring the willingness and curiosity to delve into an interesting interdisciplinary research topic in theoretical computer science, which makes use of tools from several domains of mathematics. As stated above, we aim for a rigorous understanding of infection processes and we want you to contribute to that ambitious endeavor.

What you can expect from us

We will gently introduce you to the field and (some of) the existing literature and accompany you along this interesting journey. This will be a team effort, and we aim for publishing the results together with you at a renowned international conference.

How you can contact us

Talking about infections, we can only offer you to send us an e-mail right now. However, there will also be a Q&A Zoom meeting on February 12th at 11:00 a.m. The meeting-ID is 64143774571, and the password is 99100595.

Sources

[1]	A. Christakis, Nicholas; H. Fowler, James (2015): Progression of flu contagion in the friendship network over time. Figure can be found here.
[2]	Borgs, C., Chayes, J., Ganesh, A. and Saberi, A., 2010. How to distribute antidote to control epidemics. Random Structures \& Algorithms. A free version can be found here.