zbMATH — the first resource for mathematics

On the expected total number of infections for virus spread on a finite network. (English) Zbl 1322.60206
Summary: In this work we consider a simple SIR infection spread model on a finite population of \(n\) agents represented by a finite graph \(G\). Starting with a fixed set of initial infected vertices the infection spreads in discrete time steps, where each infected vertex tries to infect its neighbors with a fixed probability \(\beta\in(0,1)\), independently of others. It is assumed that each infected vertex dies out after a unit time and the process continues till all infected vertices die out. This model was first studied by M. Draief et al. [Ann. Appl. Probab. 18, No. 2, 359–378 (2008; Zbl 1137.60051)]. In this work, we find a simple lower bound on the expected number of ever infected vertices using a breath-first search algorithm and show that it asymptotically performs better for a fairly large class of graphs than the upper bounds obtained in [loc. cit.]. As a by product, we also derive the asymptotic value of the expected number of the ever infected vertices when the underlying graph is the random \(r\)-regular graph and \(\beta<\frac{1}{r-1}\).
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J80 Branching processes (Galton-Watson, birth-and-death, etc.)
60J85 Applications of branching processes
05C80 Random graphs (graph-theoretic aspects)
92D30 Epidemiology
Full Text: DOI Euclid arXiv
[1] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008 · doi:10.1007/978-3-662-09444-0_1
[2] Alon, N., Benjamini, I. and Stacey, A. (2004). Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 1727-1745. · Zbl 1046.05071 · doi:10.1214/009117904000000414 · arxiv:math/0207112
[3] Athreya, K. B. and Ney, P. E. (2004). Branching Processes . Dover Publications, Inc., Mineola, NY. · Zbl 1070.60001
[4] Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Univ. Press, Cambridge. · Zbl 0979.05003
[5] Borgs, C., Chayes, J. T., van der Hofstad, R., Slade, G. and Spencer, J. (2005). Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms 27 137-184. · Zbl 1076.05071 · doi:10.1002/rsa.20051 · arxiv:math/0401069
[6] Borgs, C., Chayes, J. T., van der Hofstad, R., Slade, G. and Spencer, J. (2005). Random subgraphs of finite graphs. II. The lace expansion and the triangle condition. Ann. Probab. 33 1886-1944. · Zbl 1079.05087 · doi:10.1214/009117905000000260 · arxiv:math/0401070
[7] Draief, M., Ganesh, A. and Massoulié, L. (2008). Thresholds for virus spread on networks. Ann. Appl. Probab. 18 359-378. · Zbl 1137.60051 · doi:10.1214/07-AAP470
[8] Grimmett, G. (1999). Percolation , 2nd ed. Springer, Berlin. · Zbl 0926.60004
[9] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York.
[10] Kozma, G. and Nachmias, A. (2011). A note about critical percolation on finite graphs. J. Theoret. Probab. 24 1087-1096. · Zbl 1235.60138 · doi:10.1007/s10959-010-0283-x · arxiv:0909.4351
[11] Wästlund, J. (2012). Replica symmetry of the minimum matching. Ann. of Math. (2) 175 1061-1091. · Zbl 1262.91046 · doi:10.4007/annals.2012.175.3.2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.