ON THE EXPECTED TOTAL NUMBER OF INFECTIONS FOR VIRUS SPREAD ON A FINITE NETWORK

• 成果类型: Article
• 署名作者: Bandyopadhyay, Antar; Sajadi, Farkhondeh
• 署名单位: Indian Statistical Institute; Indian Statistical Institute Delhi
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/14-AAP1007
• 发表日期: 2015
• 页码: 663-674
• 关键词: random subgraphs; graphs

摘要

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 is an element of (0, 1), independently of others. It is assumed that each infected vertex dies out after an unit time and the process continues till all infected vertices die out. This model was first studied by [Ann. AppL Probab. 18 (2008) 359-378]. In this work we find a simple lower bound on the expected number of ever infected vertices using breath-first search algorithm and show that it asymptotically performs better for a fairly large class of graphs than the upper bounds obtained in [Ann. AppL Probab. 18 (2008) 359-378]. 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 < 1/r-1.