Abstract
The robustness of a network is depending on the type of attack we are considering. In this paper we focus on the spread of viruses on networks. It is common practice to use the epidemic threshold as a measure for robustness. Because the epidemic threshold is inversely proportional to the largest eigenvalue of the adjacency matrix, it seems easy to compare the robustness of two networks. We will show in this paper that the comparison of the robustness with respect to virus spread for two networks actually depends on the value of the effective spreading rate τ. For this reason we propose a new metric, the viral conductance, which takes into account the complete range of values τ can obtain. In this paper we determine the viral conductance of regular graphs, complete bi-partite graphs and a number of realistic networks.
Chapter PDF
Similar content being viewed by others
References
Albert, R., Jeong, H., Barabasi, A.: Error and attack tolerance of complex networks. Nature 406, 378–382 (2000)
Bailey, N.T.J.: The Mathematical Theory of Infectious Diseases and its Applications, 2nd edn. Charlin Griffin & Company, London (1975)
Chakrabarti, D., Leskovec, J., Faloutsos, C., Madden, S., Guestrin, C., Faloutsos, M.: Information Survival Threshold in Sensor and P2P Networks. In: Proc. IEEE INFOCOM 2007, Anchorage (2007)
Coffman Jr., F.G., Ge, Z., Misra, V., Towsley, D.: Network resilience: exploring cascading failures within BGP. In: Proc. 40th Annual Allerton Conference on Communications, Computing and Control (2002)
Cvetkovic, D.M., Doob, M., Sachs, H.: Spectra of graphs, Theory and Applications, 3rd edn. Johan Ambrosius Barth Verlag, Heidelberg (1995)
Daley, D.K., Gani, J.: Epidemic modelling: An Introduction. Cambridge University Press, Cambridge (1999)
Erdős, P., Rényi, A.: On Random Graphs. I. Publicationes Mathematicae 6, 290–297 (1959)
Eugster, P.T., Guerraoui, R., Kermarrec, A.M., Massoulié, L.: From Epidemics to Distributed computing. IEEE Computer 37(5), 60–67 (2004)
Ganesh, A., Massoulié, L., Towsley, D.: The Effect of Network Topology on the Spread of Epidemics. In: Proc. IEEE INFOCOM 2005, Miami (2005)
Kephart, J.O., White, S.R.: Direct-graph epidemiological models of computer viruses. In: Proc. IEEE Computer Society Symposium on Research in Security and Privacy, pp. 343–359 (1991)
Kooij, R.E., Jamakovic, A., Van Mieghem, P., van Dam, E.R.: Robustness of networks against the spread of viruses: the role of the spectral radius. In: Proceedings of the 13th Annual Symposium of the IEEE/CVT Benelux, Liége, Belgium (2006)
Newman, M.E.J., Barabási, A.-L., Watts, D.J.: The Structure and Dynamics of Networks. Princeton University Press, Princeton (2006)
Omic, J., Kooij, R.E., Van Mieghem, P.: Virus Spread in Complete Bi-partite Graphs. In: Proc. BIONETICS 2007, Budapest (2007)
Pastor-Satorras, R., Vespignani, A.: Epidemic Spreading in Scale-Free Networks. Physical Review Letters 86(14), 3200–3203 (2001)
Paul, G., Tanizawa, T., Havlin, S., Stanley, H.E.: Optimization of robustness of complex networks. The European Physical Journal B 38(2), 187–191 (2004)
Schumm, P., Scoglio, C., Easton, T., Gruenbacher, D.: Epidemic Spreading on Weighted Contact Networks. In: Proc. of BIONETICS 2007, Budapest, Hungary (2007)
Van Mieghem, P., Omic, J., Kooij, R.E.: Virus Spread in Networks. IEEE/ACM Transactions on Networking 17(1), 1–14 (2009)
Wang, Y., Chakrabarti, D., Wang, C., Faloutsos, C.: Epidemic spreading in real networks: An eigenvalue viewpoint. In: 22nd Symposium in Reliable Distributed Computing, Florence Italy, October 6-8 (2003)
Wang, Y., Wang, C.: Modeling the Effects of Timing Parameters on Virus Propagation. In: ACM Workshop on Rapid Malcode, Washington, DC, October 27 (2003)
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 IFIP International Federation for Information Processing
About this paper
Cite this paper
Kooij, R.E., Schumm, P., Scoglio, C., Youssef, M. (2009). A New Metric for Robustness with Respect to Virus Spread. In: Fratta, L., Schulzrinne, H., Takahashi, Y., Spaniol, O. (eds) NETWORKING 2009. NETWORKING 2009. Lecture Notes in Computer Science, vol 5550. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01399-7_44
Download citation
DOI: https://doi.org/10.1007/978-3-642-01399-7_44
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01398-0
Online ISBN: 978-3-642-01399-7
eBook Packages: Computer ScienceComputer Science (R0)