Thresholds for virus spread on networks. (English) Zbl 1137.60051
Summary: 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, infected or removed (cured and no longer susceptible to infection). We characterize how the size of the population that eventually becomes infected depends on the network topology. Specifically, we show that if the ratio of cure to infection rates is larger than the spectral radius of the graph, and the initial infected population is small, then the final infected population is also small in a sense that can be made precise. Conversely, if this ratio is smaller than the spectral radius, then we show in some graph models of practical interest (including power law random graphs) that the average size of the final infected population is large. These results yield insights into what the critical parameters are in determining virus spread in networks.
MSC:
| 60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60J85 | Applications of branching processes |
| 90B15 | Stochastic network models in operations research |
References:
| [1] | Alon, N. and Spencer, J. H. (2000). The Probabilistic Method . Wiley, New York. · Zbl 0996.05001 |
| [2] | Ball, F. (1983). A threshold theorem for the Reed-Frost chain-binomial epidemic. J. Appl. Probab. 20 153-157. · Zbl 0505.92020 · doi:10.2307/3213729 |
| [3] | Ball, F., Mollison, D. and Scalia-Tomba, G. (1997). Epidemics with two levels of mixing. Ann. Appl. Probab. 7 46-89. · Zbl 0909.92028 · doi:10.1214/aoap/1034625252 |
| [4] | Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 509-512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [5] | Barbour, A. D. and Utev, S. (2004). Approximating the Reed-Frost epidemic process. Stoch. Proc. Appl. 113 173-197. · Zbl 1113.92054 · doi:10.1016/j.spa.2004.03.013 |
| [6] | Bollobás, B. (2001). Random Graphs . Cambridge Univ. Press. · Zbl 0979.05003 |
| [7] | Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 3-122. · Zbl 1123.05083 · doi:10.1002/rsa.20168 |
| [8] | Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4 5-34. · Zbl 1047.05038 · doi:10.1007/s00493-004-0002-2 |
| [9] | Berger, N., Borgs, C., Chayes, J. and Saberi, A. (2005). On the spread of viruses on the internet. In Proc. Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms 301-310. SIAM, Philadelphia. · Zbl 1297.68029 |
| [10] | Chung, F. and Lu, L. (2002). Connected components in random graphs with given degree sequences. Ann. Combinatorics 6 125-145. · Zbl 1009.05124 · doi:10.1007/PL00012580 |
| [11] | Chung, F. and Lu, L. (2003). The average distances in random graphs with given expected degrees. Internet Math. 1 91-114. · Zbl 1065.05084 · doi:10.1080/15427951.2004.10129081 |
| [12] | Chung, F., Lu, L. and Vu, V. (2003). Eigenvalues of random power law graphs. Ann. Combinatorics 7 21-33. · Zbl 1017.05093 · doi:10.1007/s00026-003-0178-y |
| [13] | Costa, M., Castro, M., Crowcroft, J., Rowstron, A., Zhou, L., Zhang, L. and Barham, P. (2005). Vigilante: End-to-end containment of Internet worms. In Proc. Twentieth ACM Symp. on Operating Systems Principles 133-147. ACM Press, New York. |
| [14] | Erdős, P. and Renyi, A. (1960). On the evolution of random graphs. Mat Kutato Int. Közl 5 17-60. · Zbl 0103.16301 |
| [15] | Faloutsos, M., Faloutsos, P. and Faloutsos, C. (2003). Power laws and the AS-level Internet topology. IEEE/ACM Trans. Netw. 11 514-524. · Zbl 0659.68125 |
| [16] | Ganesh, A., Massoulié, L. and Towley, D. (2005). The effect of network topology on the spread of epidemics. In Proceedings IEEE Infocom . |
| [17] | Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs . Wiley, New York. · Zbl 0968.05003 |
| [18] | Kermack, W. O. and McKendrick, A. G. (1927). A contribution to the mathematical theory of epidemics. Proc. Roy. Soc. Lond. A 115 700-721. · JFM 53.0517.01 |
| [19] | Lefevre, C. and Utev, S. (1995). Poisson approximation for the final state of a generalized epidemic process. Ann. Probab. 23 1139-1162. · Zbl 0833.60023 · doi:10.1214/aop/1176988177 |
| [20] | Lovász, L. and Szegedy, B. (2004). Limits of dense graph sequences. Technical Report TR-2004-79, Microsoft Research. · Zbl 1113.05092 |
| [21] | Molloy, M. and Reed, B. A. (1995). A critical point for random graphs with a given degree sequence. Random Structures Algorithms 6 161-180. · Zbl 0823.05050 · doi:10.1002/rsa.3240060204 |
| [22] | Molloy, M. and Reed, B. A. (1998). The size of the largest component of a random graph on a fixed degree sequence. Combin. Probab. Comput. 7 295-306. · Zbl 0916.05064 · doi:10.1017/S0963548398003526 |
| [23] | Pastor-Satorras, R. and Vespignani, A. (2001). Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86 3200-3203. |
| [24] | Pastor-Satorras, R. and Vespignani, A. (2002). Epidemic dynamics in finite scale-free networks. Phys. Rev. E 65 . |
| [25] | Weaver, N., Paxson, V., Staniford, S. and Cunningham, R. (2003). A taxonomy of computer worms. In ACM Workshop on Rapid Malcode ( WORM ) 11-18. ACM Press, New York. |
| [26] | Williamson, M. M. (2002). Throttling viruses: Restricting propagation to defeat malicious mobile code. In Proc. 18th Annual Computer Security Applications Conference 1-61. IEEE Comput. Soc., Washington. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
