Infection Modeling — Part 3Optimizing a vaccination strategy with network scienceMark DitsworthBlockedUnblockFollowFollowingJan 22In part 1 of this series, we modeled the spread of a pathogen through a social network and determined that an R0 between 2–3 is most likely, with roughly 80% of the network becoming infected at some point.
In part 2, we used a genetic algorithm (GA) to identify a vaccination strategy that minimizes the spread of the infection, assuming only 25% of the population can receive a vaccine.
The resulting strategy lowered the range of likely R to 0.
68–1.
36, but with high computational cost.
In this article we will see how network analysis can be employed to achieve reductions in the pathogen’s spread, but with much more computational efficiency.
Determining the vital nodesOptimizing a vaccination policy involves identifying the most influential or important nodes in the social network.
And determining the relative importance of a node in a network is accomplished with centrality metrics.
The simplest centrality is degree centrality, which is just the node’s degree.
Eigenvector centrality measures a node’s importance by that of it’s neighbors.
The intuition of this is that a node can be important just by being connected to other important nodes.
The betweenness centrality of a node is the fraction of all geodesics that pass through that node.
The top fifteen nodes ranked by each of these centralities will be selected for vaccination.
The vaccination strategies are compared among each other, using the strategy from part 2, to determine which centrality measure is best for limiting the spread of infection.
Vaccinating by Eigenvector CentralityRanking nodes by eigenvector centrality causes nodes adjacent to high-degree nodes to be ranked higher than they would be if only degree was considered.
Sometimes low degree nodes can have more influence in the network than is suggested by degree centrality alone.
Figure 1.
PDF of R resulting from a vaccination strategy based on eigenvector centrality.
However, vaccinating based on eigenvector centrality led to poor results, as shown in Figure 1.
The range of likely R evaluated to between 0.
98 and 1.
84; worse than the result of the GA optimization.
Strongly connected clusters of nodes tend to have similar eigenvector centralities and are likely to be next to each other when ranked.
When the top 25% of nodes are selected for vaccination, it is likely that many of these nodes are part of the same cluster(s) of nodes, thereby leaving other clusters more vulnerable.
Essentially, we are selecting nodes for vaccination that are only important because the are adjacent to important nodes, leaving other nodes that actually structurally important un-vaccinated; hence the relatively poor performance.
Vaccinating by Betweenness CentralityVaccinating nodes based on betweenness centrality is attractive due to the tendency to lengthen the distance between nodes.
Nodes with high betweenness serve as intermediaries between several pairs of nodes.
Removing such a node means that the pathogen will need to traverse through more nodes to get from point A to point B.
Overall, removing the highest-ranked nodes by betweenness centrality will decrease the overall connectivity of the network, which will make it more difficult for the pathogen to spread.
Figure 2.
PDF of R resulting from a vaccination strategy based on betweenness centrality.
Removing nodes based on betweenness centrality proved slightly more effective that the GA policy.
The range of likely R evaluated to between 0.
45 and 1.
33.
Note that the Gaussian distribution in Figure 2 is less representative of the measured distribution compared to previous results.
The left tail values are more prevalent in the simulations, relative to the average values.
Vaccinating by Degree CentralityVaccinating nodes based on their degree centrality is attractive since the nodes with highest degree have the most reach across the network.
Like with betweenness centrality, removing high-degree nodes reduces the connectivity of the network.
Figure 3.
PDF of R resulting from a vaccination strategy based on degree centrality.
Figure 4.
Histogram of the number of total infected nodes resulting from each vaccination strategy.
As shown in Figure 3, the expected R is between 0.
36 and 1.
01, when using the fitted normal distribution.
However, it is evident that the the normal distribution is not a good representation of the data.
R between 0 and 0.
125 are nearly twice as prevalent in the Monte Carlo simulations as any other bin.
Looking at the histograms of the total number of infected nodes resulting from each vaccination strategy (Figure 4), we can see that the distribution seems to approach more of an exponential or power distribution.
Vaccinating by degree centrality leads to the best outcome.
Probably.
ConclusionsThe vaccination strategies based on betweenness centrality and degree centrality resulted in the expected R below 1, indicating that one of these policies would be best suited for minimizing the impact of the pathogen.
Whereas vaccinating by eigenvector centrality led to worse results than the policy determined by GA.
This is not to say that GA cannot find the optimal policy; just that it is likely to take much longer.
In part 2 we saw that it took 48 hours to converge to the given policy.
Selecting the most vital nodes in terms of eigenvector centrality, betweenness centrality, and degree centrality took 625 microseconds, 3.
44 milliseconds, and 113 microseconds, respectively.
Compared to global search algorithms in instances such as this, the tools of network science can lead to higher performing and faster results.
.