We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
1/2012
Efficiently approximating the expected number of infections in disease spreading models
Frank Bauer and Joseph Lizier
Abstract
The problem of identifying the most effective nodes in a network for seeding disease spreading (or other types of information spreading such as rumours) has gained much recent attention. Exact solutions to this problem are possible but computationally prohibitive.
Several approximation methods have been proposed. Ideally, such a method should accurately infer the number of resulting infections from each initially infected node, therefore also accurately order nodes in terms of their spreading effectiveness, and be computationally efficient. The previously proposed methods (based on degree, k-shell decomposition analysis and different centrality measures) are not usually based on the underlying disease spreading problem, rather measures of network topology. As such, they typically infer only the ordering of effectiveness of nodes but do not estimate number of infections, and indeed there is potential for the ordering they infer to be improved. We introduce a new method to approximate the number of infections resulting from a given initially infected node, based on counting the number of paths of various lengths (and in particular, self-avoiding walks for SIR models) to each other node in the network. This provides an advance over existing inference methods by taking the underlying problem into account and therefore providing estimation of actual numbers of infections.
Additionally, in simulating infections on various real-world networks with the SIR model, we show that our self-avoiding walks based method improves the inference of effectiveness of nodes over a wide range of infection rates compared to existing methods. We also analyse the trade-off between estimate accuracy and computational cost of our method, showing that good accuracy can be obtained at reasonable cost.
