Virus spread in networks

ABSTRACT

The influence of the network characteristics on the virus spread is analyzed in a new--the N-intertwined Markov chain--model, whose only approximation lies in the application of mean field theory. The mean field approximation is quantified in detail. The N-intertwined model has been compared with the exact 2^N-state Markov model and with previously proposed "homogeneous" or "local" models. The sharp epidemic threshold τc, which is a consequence of mean field theory, is rigorously shown to be equal to τc = 1/(λmax (A)), where λmax (A) is the largest eigenvalue--the spectral radius--of the adjacency matrix A. A continued fraction expansion of the steady-state infection probability at node j is presented as well as several upper bounds.

REFERENCES

• 1: R. Albert, H. Jeong, and A.-L. Barabsi, "Error and attack tolerance of complex networks," Nature, vol. 406, pp. 378-382, Jul. 27, 2000.
• 2: C. Asavathiratham, "The influence model: A tractable representation for the dynamics of networked Markov chains," Ph.D. dissertation, Dept. Electr. Eng. Comput. Sci., Mass. Inst. of Technol., Cambridge, MA, Oct. 2000.
• 3: N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and Its Applications, 2nd ed. London, U.K.: Charlin Griffin, 1975.
• 4: G. S. Canright and K. Engø-Monsen, "Spreading on networks: A topographic view," in Proc. ComPlexUs, Aug. 2006, vol. 3, pp. 131-146.
• 5: D. M. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs, Theory and Applications, 3rd ed. Heidelberg, Germany: Johan Ambrosius Barth Verlag, 1995.
• 6: D. J. Daley and J. Gani, Epidemic Modelling: An Introduction. Cambridge, U.K.: Cambridge Univ. Press, 1999.
• 7: G. F. D. Duff and D. Naylor, Differentiation Equations of Applied Mathematics. New York: Wiley, 1966.
• 8: R. Durrett and X.-F. Liu, "The contact process on a finite set," Annals Probabil., vol. 16, no. 3, pp. 1158-1173, 1988.
• 9: A. Ganesh, L. Massoulié, and D. Towsley, "The effect of network topology on the spread of epidemics," in Proc. IEEE INFOCOM 2005, Miami, FL, Mar. 2005, vol. 2, pp. 1455-1466.
• 10: M. Garetto, W. Gong, and D. Towsley, "Modeling malware spreading dynamics," in Proc. IEEE INFOCOM 2003, San Francisco, CA, Mar. 2003, vol. 3, pp. 1869-1879.
• 11: J. O. Kephart and S. R. White, "Directed-graph epidemiological models of computer viruses," in Proc. IEEE Comput. Soc. Symp. Research in Security and Privacy, May 1991, pp. 343-359.
• 12: R. Pastor-Satorras and A. Vespignani, "Epidemic spreading in scale-free networks," Phys. Rev. Lett., vol. 86, no. 14, pp. 3200-3203, Apr. 2001.
• 13: Romualdo Pastor-Satorras , Alessandro Vespignani, Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, New York, NY, 2004
• 14: Piet Van Mieghem, Performance Analysis of Communications Networks and Systems, Cambridge University Press, New York, NY, 2005
• 15: Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos, "Epidemic spreading in real networks: An eigenvalue viewpoint," in Proc. 22nd Int. Symp. Reliable Distributed Systems (SRDS'03), Oct. 2003, pp. 25-34.
• 16: Yang Wang , Chenxi Wang, Modeling the effects of timing parameters on virus propagation, Proceedings of the 2003 ACM workshop on Rapid malcode, October 27-27, 2003, Washington, DC, USA [doi>10.1145/948187.948198]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Security

Keywords:
Markov theory, epidemic threshold, mean field theory, spectral radius, virus spread