article

Virus spread in networks

Authors:

Piet Van Mieghem,

Robert KooijAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 17, Issue 1

Pages 1 - 14

https://doi.org/10.1109/TNET.2008.925623

Published: 01 February 2009 Publication History

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]

R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet, A Statistical Physics Approach. Cambridge, U.K.: Cambridge Univ. Press, 2004.

Digital Library

[14]

P. Van Mieghem, Performance Analysis of Communication Systems and Networks. Cambridge, U.K.: Cambridge Univ. Press, 2006.

Digital Library

[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]

Y. Wang and C. Wang, "Modeling the effects of timing parameters on virus propagation," in Proc. ACM Workshop Rapid Malcode (WORM'03), Washington, DC, Oct. 27, 2003, pp. 61-66.

Digital Library

Cited By

Dwivedi DMitikiri SBabu KYemula PSrinivas VChakraborty PPal M(2024)Technological advancements and innovations in enhancing resilience of electrical distribution systemsInternational Journal of Critical Infrastructure Protection10.1016/j.ijcip.2024.10069646:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.ijcip.2024.100696
Muthukumar SSenthilkumar MVeeramani C(2024)Optimal Control of Computer Virus Spreading Model with Partial ImmunizationWireless Personal Communications: An International Journal10.1007/s11277-024-11013-6134:4(2287-2313)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s11277-024-11013-6
Xu WZhang Z(2023)Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover TimeACM Transactions on Knowledge Discovery from Data10.1145/358369117:7(1-19)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3583691
Show More Cited By

Recommendations

Adaptive Epidemic Dynamics in Networks: Thresholds and Control
Special Section on Best Papers from SEAMS 2012

Theoretical modeling of computer virus/worm epidemic dynamics is an important problem that has attracted many studies. However, most existing models are adapted from biological epidemic ones. Although biological epidemic models can certainly be adapted ...
Thresholds for virus spread on networks
valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

We study how the spread of computer viruses, worms, and other self-replicating malware is affected by the logical topology of the network over which they propagate. We consider a model in which each host can be in one of 3 possible states - susceptible, ...
Epidemic thresholds in real networks

How will a virus propagate in a real network? How long does it take to disinfect a network given particular values of infection rate and virus death rate? What is the single best node to immunize? Answering these questions is essential for devising ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 17, Issue 1

February 2009

346 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 February 2009

Revised: 20 July 2007

Received: 23 March 2007

Published in TON Volume 17, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

84
Total Citations
View Citations
963
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dwivedi DMitikiri SBabu KYemula PSrinivas VChakraborty PPal M(2024)Technological advancements and innovations in enhancing resilience of electrical distribution systemsInternational Journal of Critical Infrastructure Protection10.1016/j.ijcip.2024.10069646:COnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.ijcip.2024.100696
Muthukumar SSenthilkumar MVeeramani C(2024)Optimal Control of Computer Virus Spreading Model with Partial ImmunizationWireless Personal Communications: An International Journal10.1007/s11277-024-11013-6134:4(2287-2313)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s11277-024-11013-6
Xu WZhang Z(2023)Optimal Scale-Free Small-World Graphs with Minimum Scaling of Cover TimeACM Transactions on Knowledge Discovery from Data10.1145/358369117:7(1-19)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3583691
Chai YWang Y(2023)Optimal Control of Information Diffusion in Temporal NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2022.320999420:1(104-119)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TNSM.2022.3209994
Lorch LKremer HTrouleau WTsirtsis SSzanto ASchölkopf BGomez-Rodriguez M(2022)Quantifying the Effects of Contact Tracing, Testing, and Containment Measures in the Presence of Infection HotspotsACM Transactions on Spatial Algorithms and Systems10.1145/35307748:4(1-28)Online publication date: 2-Nov-2022
https://dl.acm.org/doi/10.1145/3530774
Singh SAlajaji FGharesifard B(2022)Modeling Network Contagion Via Interacting Finite Memory Pólya Urns2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834759(348-353)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834759
Peng XLi CQi HSun GWang ZWu Y(2022)Competition between awareness and epidemic spreading in homogeneous networks with demographyApplied Mathematics and Computation10.1016/j.amc.2021.126875420:COnline publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.amc.2021.126875
Bazgan CBeaujean PGourdin É(2022)An approximation algorithm for the maximum spectral subgraph problemJournal of Combinatorial Optimization10.1007/s10878-020-00552-w44:3(1880-1899)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10878-020-00552-w
Tsemogne OHayel YKamhoua CDeugoué G(2022)Optimizing Intrusion Detection Systems Placement Against Network Virus Spreading Using a Partially Observable Stochastic Minimum-Threat Path GameDecision and Game Theory for Security10.1007/978-3-031-26369-9_14(274-296)Online publication date: 26-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-26369-9_14
Wang KLiu XGuo D(2021)High-Order Mean-Field Approximations for Adaptive Susceptible-Infected-Susceptible Model in Finite-Size NetworksComplexity10.1155/2021/66377612021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/6637761
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents