by Dirk Brockmann
This explorable illustrates and compares three vaccination strategies in complex networks. In this type of model nodes are people and network links potential transmission paths. “Vaccination” then means that nodes are disconnected from the network because they can no longer acquire or transmit a disease. Vaccination thus effectively dilutes the network. Two strategies, A and B, are straightforward to understand. A third one, C, is a bit odd and counterintuitive at first glance:
- strategy A: A set of nodes is chosen at random and vaccinated
- strategy B: The most connected nodes are chosen and vaccinated
- strategy C: A set of nodes is chosen at random and then one of each node’s neighbors is vaccinated
Intuitively we expect strategy B to be more efficient than A and C and this is indeed so. Strategy A and C, however, sound equivalent. But they are not. In fact, strategy C is more effective than strategy A. The reason for this will be explained below.
To get most out of this explorable, try following the sequence of experiments outlined below.
This is how it works
In the display you see a network of 200 individuals. The network has one component so if a contagion process were to advance through this network eventually every node could be affected. Highly connected individuals are displayed a bit larger than those with a small number of links. The connectivity of a node is measure by its degree the number of links (neighbors) it has.
When you vaccinate a fraction (slider) of the population by pressing one of the large buttons, a set of nodes will be disconnected from the network. For low vaccination the network doesn’t change much. If the fraction is sufficiently large the network will be disconnected.
The large buttons correspond to the three strategies above. When you press them once, vaccination will be performed. Pressing them again will reset the network.
Turn the vaccination slider to about 38%. Now press button A. You should see that all the vaccinated individuals are now isolated and move to the periphery. Yet, a considerable fraction of the network is still in one large component (check out the explorable Blob to learn about giant components in networks), the network hasn’t really disintegrated, because 38% is too low for this strategy.
Press the button again to reset the system.
Now try strategy B. In this case high degree nodes are removed. As expected, in this scenario the network becomes very sparse and even the largest component is very small. Removing high degree nodes, we effectively remove many more links. The network falls apart.
Note also that among the isolated nodes, many aren’t vaccinated. This effect is called herd-immunity, the indirect isolation of nodes.
The problem in reality is, though, that we often do not know who the high degree superspreaders are. Well, let’s try strategy C…..
Here’s now a clever strategy. Press button C. Again, a random set of nodes is picked but instead of vaccinating these nodes, we vaccinate a random neighbor of each of them. So we remove the same number of nodes as in the other two strategies.
However, by comparing the size of the largest component in strategy A and C, we see that typically this largest component is significantly smaller for C than for A. Therefore strategy C is more effective!
What is happening?
Your friends have more friends than you
A peculiar property of complex networks, especially those with heterogeneous node connectivity, is that on average a node’s neighbors’ degree is larger than the node’s own degree. This is known as the friendship paradox. When reading this, it sounds almost schizophenic. Why should my “friend” exhibit different properties? After all I am my friend’s friend, too?
It turns out that the secret is hidden in the term “on average” and that we are comparing different averages. In one case we are averaging over nodes, in the other case we are averaging over links. Another way of thinking about it is this: When we pick a random set of nodes, (strategy A), the probability of say picking node $n$ is the same for all nodes, $1/N$ for each node. When we pick a random neighbor of a random node, the probability of picking a node is proportional to the target node’s degree $q$ so we are not sampling the nodes uniformly. We are more likely to pick a node with higher degree.
If one does the math for this, one can show that the mean degree of a neighbor $q_0$ is given by
$$ q_0 = (1+\sigma^2) k_0 $$
where $k_0$ is the mean node degree and $\sigma^2$ the variance in node degree. This equation states that a neighbor’s node degree is always larger than the average node degree, the effect is stronger for networks with broad degree distributions.
Erdős–Rényi & Barabási–Albert
In the control panel you can chose two different types of networks, the Barabási–Albert (BA) and the Erdős–Rényi (ER) network. The BA network has a much stronger variation in node degree compared to the ER network. Therefore the effects explained above should be stronger in the BA network.
R. Albert, H. Jeong, A.-L. Barabási, Error and attack tolerance of complex networks, Nature, 406, pages 378–382 (27 July 2000
R. Cohen, S. Havlin, D. ben-Avraham, Efficient Immunization Strategies for Computer Networks and Populations, Phys. Rev. Lett. 91, 247901