Combinatorics Seminar 2015

Speaker: Dominik Scheder (謝德明), Shanghai Jiao Tong University

Date: Thu, Jan 14, 2016

Time: 15:30 - 16:30

Venue: Middle Meeting Room

Title: Which networks are optimal for epidemic control?


Here is a crude model of how a virus spreads in a network. At each site of the network, the number of infected people doubles in each time step. The infected people still walk/drive/fly around, from their current site to neighboring sites. This can be modeled by a Markov chain: Let $x$ be a vector describing the number of infected people and $A$ a stochastic matrix describing the travel patterns of people. Then $2Ax$ describes the number of infected people in the next time step.

Some people are vaccinated: Let's say a $v_i$ fraction of people at site $i$ is vaccinated, meaning the virus cannot infect them. Let $D$ be the $n\times n$ diagonal matrix with $d_{i,i} := 1-v_i$. Then the number of infected people in the next time step is $2ADx$.

Note that the virus becomes epidemic if $(2AD)^t$ diverges, i.e., if the largest eigenvalue of $AD$ is $\geq 0.5$.

Question 1: Given a stochastic matrix $A$, what is the smallest percentage of people we have to vaccinate to prevent an epidemic? Here we assume that there is an equal number of people living at each site.

The next question is much weirder, due to the original problem that motivated the above.

Question 2: Suppose we can not only design the vaccination policy, but also the network itself, i.e., the matrix $A$, but under two constraints: (1) The matrix is doubly stochastic (this is roughly realistic: the expected amount of people arriving at site $u$ should be equal to the amount leaving site $u$); (2) the matrix is of the form $(B+U)/2$, where $B$ is doubly stochastic and $U$ is the uniform matrix having entry $1/n$ everywhere. Note that $U$ corresponds to a Markov chain where people travel to a completely random location.

Which matrix $B$ allows the cheapest vaccination policy?

Conjecture: The optimal $B$ is the matrix describing a walk in a directed $3$-cycle, i.e., $$ B= \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ \end{bmatrix}, $$ and exactly a third of the population has to be vaccinated in this case.

By the way, my motivation to study this problem comes not from epidemics but from Satisfiability algorithms.