What nodes of a graph should be vaccinated first?

Question

Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node). Choose some random number "K" of nodes which are "infected" initially. So we can generate epidemic model on a graph - each time tick - neighbors of already infected nodes become also "infected" with probability "p".

Now assume we have an option to "vaccinate" some number of nodes "V", that means they will never be infected. It is clear intuitively that it is more reasonable to "vacciante" those nodes with many neighbors, i.e. high degree nodes, however, graph theory suggests that there are several more sophisticated measures of "importance" of nodes - i.e. "centrality measures". Intuitively it corresponds to the situation that node may have many neigbours, but its neigbours have low number of neigbours, that means second step of epidemy will not be so harmful. That is why it is not obvious that direct choice of nodes with highest degrees is optimal.

Question: Is there any research on choosing relevant nodes for vaccination ? What are the outcomes ? If yes, how less effective would be the naive strategy to vaccinate nodes with the highest degrees comparing to more advanced ones ?

PS

There can be several ways to measure "effectiveness" of vaccination , as well as epidemic model may contain more parameters like - how long is node "infected", as well as answer might depend on type of a random graph considered - any information is welcome. Well, keeping real world situation in mind would be also nice.

Answer 1

Not a complete answer, but I don’t yet have enough reputation to comment: one way to measure the “importance” of a vertex w.r.t. it’s degree and the degrees of its neighbors goes by the name of shell index. Searching for that phrase plus the key term $k$-cores (sometimes called $k$-shells) will turn up a whole literature on techniques for finding "influential spreaders" in networks based on these ideas.

One way to define the $k$-core of an undirected graph $G$ is as the subgraph obtained by iteratively deleting vertices of degree less than $k$. So the $0$-core of $G$ is $G$ itself, the $1$-core is $G$ minus isolated vertices, the $2$-core of $G$ is the (unique!) maximal subgraph of $G$ with minimum degree 2, and so on. A vertex has shell index $k$ if it is in the $k$-core of $G$ but not the $(k+1)$-core. Roughly speaking, a vertex has high shell index only if it has high degree and is adjacent to many other vertices of high degree. Hopefully this gives some intuition as to why the shell index might matter for the type of question you are interested in.

Edit: See, e.g., this paper

Answer 2

I took a look at a very simple model: SIR for 2 population groups with the interaction matrix $A=\begin{bmatrix}\alpha & \lambda\\\mu & \beta\end{bmatrix}$, which, roughly speaking, corresponds to the random graph with 2 types of vertices and degrees within and between groups proportional to matrix elements). The balance in the matrix is, of course, that the group sizes are proportional to $\mu$ and $\lambda$ respectively. The objective is to stop the exponential spread with the minimal amount of vaccination at the moment $0$, which mathematically means that we can multiply the first row by $u$ and the second by $v$ (not vaccinated parts, both in $[0,1]$) so that the maximal eigenvalue gets below the recovery rate (say, $1$) and we want to maximize $\mu u+\lambda v$.

The answer here is simple and explicit: if $\alpha>\mu$ and $\beta>\lambda$, then $u=\frac{\beta-\lambda}D, v=\frac{\alpha-\mu}D$ where $D=\alpha\beta-\lambda\mu$ is the determinant of $A$ as long as this is in the range. In all other cases, the answer is on the boundary.

Since $\beta-\lambda<\alpha-\mu$ if and only if $\alpha+\lambda>\beta+\mu$, for the "inner point" optimizer, this gives an advantage to vertices of higher degree, but not an absolute one (meaning that you do not need to vaccinate them all first before even touching the other group). Also, if $\alpha=\beta$ and $\mu=\lambda$ (all vertices look the same from any standpoint), the "fair" vaccination ($u=v$) is optimal only if $\alpha\ge\lambda$. Otherwise it becomes the worst you can do (some symmetric curve changes concavity).

One can play with some larger matrices too, say, a rank one matrix that would arise if all interaction was in the public transportation. Then the conclusion is that you should vaccinate frequent travelers first (not a big surprise, really) and (perhaps less obviously) that the importance of vaccination is proportional to the square of the average daily time in the transport (in the sense that if $A$ spends twice as much time as $B$ commuting, then if you don't vaccinate one $A$, you have to vaccinate four $B$'s to get the same effect.

In general my point is that it is worth considering a few very simple models and examples before you pass to complicated ones. And if you want to make some real recommendations from you models, keep in mind that we really do not know either the graph or the matrix, so any sophisticated fine tuning is totally impractical and the actual question seems to be if one can devise some simple strategy using only observable quantities that works "most of the time" and to point out the exceptions to it. Anyway, good luck!

Answer 3

This is a much studied question, at the crossroad of several fields: epidemiology, mathematics, statistical mechanics, and computer science, at least.

The model you consider is known as SI with parameter p, of which many variants exist.

The vaccination problem is very similar to the robustness problem: how many nodes may be removed from a network without breaking connectivity for most nodes. Here, the main criterion is the size of the largest connected component, seen as a bound for the size of any epidemics.

The problem is also related to the influence maximization problem, where one seeks for (sets of) nodes in a network that may effectively spread an information.

Mathematical approaches to all these problems are strongly related to the study of connected components in various kinds of random graphs. A much regarded question is the influence of the graph degree distribution, with various interesting threshold effects.

An approach that I like claims that, if you have no global knowledge of your network, then you should choose random nodes and ask them to cite a random person. This person is likely to have many contacts (the probability that it is cited is proportional to the number of persons knowing her), more than random individuals, and so she is a good vaccination target.

It is hard to choose among the many references I may cite on this topic, but I suggest the 2008 book "Dynamical Processes on Complex Networks" by Barrat, Barthélémy and Vespignani, Cambridge University Press, as well as our survey paper "Impact of random failures and attacks on Poisson and power-law random networks" published in ACM Computing Surveys. You may also search the web for the topics above.

Many recent approaches leverage mobility traces and try to incorporate temporal information in addition to graph information, see for instance the COVID-19 Mobility Network Modeling project at Stanford.

Answer 4

Not an answer, but too long for a comment. I guess the answer depends a lot on which graph you consider. Maybe you can solve the problem for some very specific graphs (for example a random graph).

If you want to consider the current pandemic it is important to notice that the vertex distribution is very unequal. Some folk lore seems to be that 20% have 80% of the contacts. This is also (partly) reflected in the super-spreading nature of the pandemic. However there is it not just the distribution of contacts that is an indicating of super-spreading, but also the individual transmissibility. You could ask whether it is possible to model this phenomena by changing the graph.
(One reference: https://www.medrxiv.org/content/10.1101/2020.09.15.20195008v3)

Concerning your question of measuring the effectiveness of "vaccination". You could think of a model where you assign a "severity" parameter to each vertex indicating the potential severity of the infection. Then you should not try to minimise the total number of the infected vertices but the sum of the severities of the infected vertices. Of course here it seems again that to solve the problem you need a specific model of a graph (where it would be natural that the severity and the degree of the vertices are negatively correlated).

Of course policy makers are struggling unrigorously with this problem right now. With three different approaches: Vaccination of high severity numbers (people at risk), vaccination of neighbours of high severity numbers (as care-workers) and vaccination of demographic groups with high degree (young people). Focussing on particularly dense part of the graph (as big cities and special demographics). Hospital staff do not seem to fit well into the model.