Three faces of node importance in network epidemiology: Exact results for small graphs

Abstract

We investigate three aspects of the importance of nodes with respect to Susceptible-Infectious-Removed (SIR) disease dynamics: influence maximization (the expected outbreak size given a set of seed nodes), the effect of vaccination (how much deleting nodes would reduce the expected outbreak size) and sentinel surveillance (how early an outbreak could be detected with sensors at a set of nodes). We calculate the exact expressions of these quantities, as functions of the SIR parameters, for all connected graphs of three to seven nodes. We obtain the smallest graphs where the optimal node sets are not overlapping. We find that: node separation is more important than centrality for more than one active node, that vaccination and influence maximization are the most different aspects of importance, and that the three aspects are more similar when the infection rate is low.

arXiv comment(v3: thoroughly revised)

References in corpus (11)

• Epidemic processes in complex networks
• Immunization of complex networks
• Vital nodes identification in complex networks
• Statistical physics of vaccination
• Social Network Sensors for Early Detection of Contagious Outbreaks
• Optimizing surveillance for livestock disease spreading through animal movements
• Contact tracing and epidemics control in social networks
• Cost-efficient vaccination protocols for network epidemiology
• Fundamental difference between superblockers and superspreaders in networks
• Ranking influential spreaders is an ill-defined problem
• Directionality of contact networks suppresses selection pressure in evolutionary dynamics

Cited by in corpus (13)

• Beyond ranking nodes: Predicting epidemic outbreak sizes by network centralities
• Fast and principled simulations of the SIR model on temporal networks
• Immunization Strategies in Networks with Missing Data
• Interplay between cost and benefits triggers nontrivial vaccination uptake
• Objective measures for sentinel surveillance in network epidemiology
• Epidemic extinction in networks: Insights from the 12,110 smallest graphs
• Statistical Analysis of Tipping Pathways in Agent-Based Models
• Vaccination strategies on dynamic networks with indirect transmission links and limited contact information
• Influence Maximization: Divide and Conquer
• Exact analytical solution of irreversible binary dynamics on networks
• The role of susceptible individuals in spreading dynamics
• Group centrality in optimal and suboptimal vaccination for epidemic models in contact networks
• Diffusion on dynamic contact networks with indirect transmission links