2nd International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems

Research Article

Virus spread in complete bi-­partite graphs

Download77 downloads
  • @INPROCEEDINGS{10.4108/ICST.BIONETICS2007.2399,
        author={J.S. Omic and R. E. Kooij and P.  Van Mieghem},
        title={Virus spread in complete bi-­partite graphs},
        proceedings={2nd International ICST Conference on Bio-Inspired Models of Network, Information, and Computing Systems},
        proceedings_a={BIONETICS},
        year={2008},
        month={8},
        keywords={Computer Virus  Epidemiology  Modeling  Simulation},
        doi={10.4108/ICST.BIONETICS2007.2399}
    }
    
  • J.S. Omic
    R. E. Kooij
    P. Van Mieghem
    Year: 2008
    Virus spread in complete bi-­partite graphs
    BIONETICS
    ICST
    DOI: 10.4108/ICST.BIONETICS2007.2399
J.S. Omic1,*, R. E. Kooij1,2,*, P. Van Mieghem1,*
  • 1: Faculty of Electrical Engineering, Mathematics, and Computer Science Delft University of Technology, P.O. Box 5031, 2600 GA Delft
  • 2: TNO Information and Communication Technology, P.O. Box 5050, 2600 GB Delft, The Netherlands
*Contact email: j.s.omic@ewi.tudelft.nl, robert.kooij@tno.nl, p.vanmieghem@ewi.tudelft.nl

Abstract

In this paper we study the spread of viruses on the complete bi-partite graph KM,N. Using mean field theory we first show that the epidemic threshold for this type of graph satifies tauc = 1/radic(MN), hence, confirming previous results from literature. Next, we find an expression for the average number of infected nodes in the steady state. In addition, our model is improved by the introduction of infection delay. We validate our models by means of simulations. Inspired by simulation results, we analyze the probability distribution of the number of infected nodes in the steady state for the case without infection delay. The mathematical model we obtain is able to predict the probability distribution very well, in particular, for large values of the effective spreading rate. It is also shown that the probabilistic analysis and the mean field theory predict the same average number of infected nodes in the steady state. Finally, we present a heuristic for the prediction of the extinction probability in the first phase of the infection. Simulations show that, for the case without infection delay, this time dependent heuristic is quite accurate.