Abstract
Serious epidemics, both in cyber space as well as in our real world, are expected to occur with high probability, which justifies investigations in virus spread models in (contact) networks. The N-intertwined virus spread model of the SIS-type is introduced as a promising and analytically tractable model of which the steady-state behavior is fairly completely determined. Compared to the exact SIS Markov model, the N-intertwined model makes only one approximation of a mean-field kind that results in upper bounding the exact model for finite network size N and improves in accuracy with N. We review many properties theoretically, thereby showing, besides the flexibility to extend the model into an entire heterogeneous setting, that much insight can be gained that is hidden in the exact Markov model.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Anderson RM, May RM (1991) Infectious diseases of humans: dynamics and control. Oxford University Press, Oxford
Asavathiratham C (2000) The influence model: a tractable representation for the dynamics of networked markov chains. Ph.D thesis, Massachusetts Institute of Technology, Cambridge
Bailey NTJ (1975) The mathematical theory of infectious diseases and its applications, 2nd edn. Charlin Griffin & Company, London
Barrat A, Bartelemy M, Vespignani A (2008) Dynamical processes on complex networks. Cambridge University Press, Cambridge
Biggs N (1996) Algebraic graph theory, 2nd edn. Cambridge University Press, Cambridge
Castellano C, Pastor-Satorras R (2010) Thresholds for epidemic spreading in networks. Phys Rev Lett 105: 218701
Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Trans Inf Syst Secur (TISSEC) 10(4): 1–26
Chen Y, Paul G, Havlin S, Liljeros F, Stanley HE (2008) Finding a better immunization strategy. Phys Rev Lett 101: 058701
Cvetković DM, Doob M, Sachs H (1995) Spectra of fraphs, theory and applications, 3rd edn. Johann Ambrosius Barth Verlag, Heidelberg
Daley DJ, Gani J (1999) Epidemic modelling: an introduction. Cambridge University Press, Cambridge
Darabi Sahneh F, Scoglio C (2011) Epidemic spread in human networks. In: 50th IEEE conference on decision and control, Orlando, December 2011. arXiv:1107.2464v1
Durrett R (2010) Some features of the spread of epidemics and information on a random graph. Proc Natl Acad Sci USA (PNAS) 107(10): 4491–4498
Ganesh A, Massoulié L, Towsley D (2005) The effect of network topology on the spread of epidemics. In: IEEE INFOCOM05, San Francisco
Garetto M, Gong W, Towsley D (2003) Modeling malware spreading dynamics. In: IEEE INFOCOM’03, San Francisco, April 2003
Gómez S, Arenas A, Borge-Holthoefer J, Meloni S, Moreno Y (2010) Discrete-time Markov chain approach to contact-based disease spreading in complex networks. Europhys Lett (EPL) 89: 38009
Gourdin E, Omic J, Van Mieghem P (2011) Optimization of network protection against virus spread. In: 8th international workshop on design of reliable communication networks (DRCN 2011), Krakow, 10–12 October 2011
Hill AL, Rand DG, Nowak MA, Christakis NA (2010) Emotions as infectious diseases in a large social network: the SISa model. Proc Royal Soc B 277: 3827–3835
Kephart JO, White SR (1991) Direct-graph epidemiological models of computer viruses. In: Proceedings of the 1991 IEEE computer society symposium on research in security and privacy, pp 343–359, May 1991
Kermack WO, McKendrick AG (1927) A contribution to the mathematical theory of epidemics. Proc Royal Soc A 115: 700–721
Kooij RE, Schumm P, Scoglio C, Youssef M (2009) A new metric for robustness with respect to virus spread. In: Networking 2009, LNCS 5550, pp 562–572
Omic J (2010) Epidemics in networks: modeling, optimization and security games. Ph.D thesis, September 2010. http://repository.tudelft.nl/. Accessed Sept 2010
Omic J, Kooij RE, Van Mieghem P (2007) Virus spread in complete bi-partite graphs. In: Bionetics 2007, Budapest, 10–13 December 2007
Omic J, Kooij RE, Van Mieghem P (2009) Heterogeneous protection in regular and complete bi-partite networks. In: IFIP networking 2009, Aachen, 11–15 May 2009
Omic J, Martin Hernandez J, Van Mieghem P (2010) Network protection against worms and cascading failures using modularity partitioning. In: 22nd international teletraffic congress (ITC 22), Amsterdam, 7–9 September 2010
Omic J, Van Mieghem P (2009) Epidemic spreading in networks—variance of the number of infected nodes. Delft University of Technology, report20090707. http://www.nas.ewi.tudelft.nl/people/Piet/TUDelftReports
Omic J, Van Mieghem P, Orda A (2009) Game theory and computer viruses. In: IEEE Infocom09
Pastor-Satorras R, Vespignani A (2001) Epidemic spreading in scale-free networks. Phys Rev Lett 86(14): 3200–3203
Restrepo JG, Ott E, Hunt Brian R (2005) Onset of synchronization in large networks of coupled oscillators. Phys Rev E 71(036151): 1–12
Strogatz SH (2000) From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators. Physica D 143: 1–20
Van Mieghem P (2006) Performance analysis of communications systems and networks. Cambridge University Press, Cambridge
Van Mieghem P (2011) Epidemic phase transition of the SIS-type in networks (submitted)
Van Mieghem P (2011) Graph spectra for complex networks. Cambridge University Press, Cambridge
Van Mieghem P (2011) Viral conductance of a network (submitted)
Van Mieghem P, Ge G, Schumm P, Trajanovski S, Wang H (2010) Spectral graph analysis of modularity and assortativity. Phys Rev E 82: 056113
Van Mieghem P, Omic J (2008) In-homogeneous virus spread in networks. Delft University of Technology, Report2008081. http://www.nas.ewi.tudelft.nl/people/Piet/TUDelftReports
Van Mieghem P, Omic J, Kooij RE (2009) Virus spread in networks. IEEE/ACM Trans Netw 17(1): 1–14
Van Mieghem P, Stevanović D, Kuipers FA, Li C, van de Bovenkamp R, Liu D, Wang H (2011) Decreasing the spectral radius of a graph by link removals. Phys Rev E 84(1): 016101
Van Mieghem P, Wang H, Ge X, Tang S, Kuipers FA (2010) Influence of assortativity and degree-preserving rewiring on the spectra of networks. E Phys J B 76(4): 643–652
Wang H, Winterbach W, Van Mieghem P (2011) Assortativity of complementary graphs. Eur Phys J B (to appear)
Wang Y, Chakrabarti D, Wang C, Faloutsos C (2003) Epidemic spreading in real networks: an eigenvalue viewpoint. In: 22nd international symposium on reliable distributed systems (SRDS’03), IEEE computer, pp 25–34, October 2003
Wang Y, Wang C (2003) Modeling the effects of timing parameters on virus propagation. In: ACM workshop on rapid malcode (WORM’03), Washington DC, pp 61–66, 27 Oct 2003
Youssef M, Kooij RE, Scoglio C (2011) Viral conductance: quantifying the robustness of networks with respect to spread of epidemics. J Comput Science. doi:10.1016/j.jocs.2011.03.001
Youssef M, Scoglio C (2011) An individual-based approach to SIR epidemics in contact networks. J Theor Biol 283: 136–144
Acknowledgments
We are very grateful to Caterina Scoglio, Mina Youssef, Faryad Darabi Sahneh, Cong Li and Rob Kooij for many comments on an early version of the manuscript. This research was supported by Next Generation Infrastructures (Bsik) and the EU FP7 project ResumeNet (project No. 224619).
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Van Mieghem, P. The N-intertwined SIS epidemic network model. Computing 93, 147–169 (2011). https://doi.org/10.1007/s00607-011-0155-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-011-0155-y