Effective immunization of online networks: a self-similar selection approach
Tóm tắt
This paper proposes a self-similar selection method as an alternative to existing immunization strategies for online networks. Given the self-similar characteristics of online networks which are shown to have fractal and scale-free structure, we presume that the self-similar selection which is well developed in physics outperforms random or targeted vaccination based on incoming or outgoing connections. We examine the effectiveness of the proposed self-similar selection method with random vaccination and other different types of targeted vaccination strategies in terms of delaying the spread of computer virus over a scale-free computer network constructed using real-world World Wide Web data. Our computer simulation results indicate that the self-similar selection method is more effective in deterring virus propagation than the existing vaccination strategies. In addition, vaccination based on self-similar selection is practical since it does not require detailed information about network morphology at the individual node level, which is often not easy to observe. Our findings have significant implications for both policy makers and network security providers.
Tài liệu tham khảo
Akoglu L, Faloutsos C (2009) RTG: a recursive realistic graph generator using random typing. Data Min Knowl Disc 19(2):194–209
Albert R, Jeong H, Barabasi AL (1999) Diameter of the world-wide web. Nature 401:130–131
Albert R, Jeong H, Barabasi AL (2000) Attack and error tolerance of complex networks. Nature 406:378–382
Bai X, Airoldi EM, Malin B (2011) An entropy approach to disclosure risk assessment: lessons from real applications and simulated domains. Decis Support Syst 51(1):10–20
Balthrop J, Forrest S, Newman ME, Willamson M (2004) Technological networks and the spread of computer viruses. Science 304:527–529
Barabasi AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509–512
Callaway DS, Newman ME, Strogatz SH, Watts DJ (2000) Network robustness and fragility: percolation on random graphs. Physical Review Letter 85:5468–5471
Chakrabarti D, Wang Y, Wang C, Leskovec J, Faloutsos C (2008) Epidemic thresholds in real networks. ACM Transactions on Information and System Security 10(4):1–26
Cohen R, Erez K, ben-Avraham D D, Havlin S (2000) Resilience of the Internet to random breakdowns. Physical Review Letter 85:4629–4632
Cohen R, Havlin S, ben-Avraham D (2003) Efficient immunization strategies for computer networks and populations. Phys Rev Lett 91(24):247901
Erdos P, Renyi A (1960) On the evolution of random graphs. Publication of the Mathematical Institute of Hungarian Academy of Sciences 5:17–61
Ganesh A, Massoulié L, Towsle D (2005) The effect of network topology on the spread of epidemics. Procedings of IEEE INFOCOM 2005:1455–1466
Gleissner W (1989) A mathematical theory for the spread of computer viruses. Computer and Security 8:35–41
Jung S, Kim S, Kahng B (2002) Geometric fractal growth model for scale-free networks. Phys Rev E 65:056101
Kim BC, Chen P, Mukhopadhyay T (2011) The effect of liability and patch release on software security: the monopoly case. Production and Operations Management 20(4):603–617
Kim BC, Chen P, Mukhopadhyay T (2010) An economic analysis of the software market with a risk-sharing mechanism. International Journal of Electronic Commerce 14(2):7–39
Kim JS, Goh KI, Kahng B, Kim D (2007) Fractality and self-similarity in scale-free networks. New J Phys 9:177
Leskovec J, Faloutsos C (2007) Scalable modeling of real graphs using Kronecker multiplication. Proceedings of the 24th international conference on machine learning 497–504
Mandelbrot BB (1983) The fractal geometry of nature. Freeman Publisher, WH
Markoff J (2009) Worm infects millions of computers worldwide. New York Times Jan 22, 2009, available online at http://www.nytimes.com/2009/01/23/technology/internet/23worm.html
Murray W (1988) The application of epidemiology to computer viruses. Computers and Security 7:35–41
Newman ME, Forrest S, Balthrop J (2002) Email networks and the spread of computer viruses. Phys Rev 66(3):035101
Oh W, Jeon S (2007) Membership herding and network stability in the open source community. Manage Sci 53(7):1086–1101
Park I, Sharman R, Rao HR, Upadhyaya S (2007) Short term and total life impact analysis of email worms in computer systems. Decis Support Syst 43(3):827–841
Song C, Havlin S, Makse HA (2005) Self-similarity of complex networks. Nature 433:392–395
Rozenfeld HD, Gallos LK, Song C, Makse HA (2008) Fractal and transfractal scale-tree networks. arXiv:0808.2206v1
Rozenfeld HD, Song C, Makse HA (2010) Small-world to fractal transition in complex networks: a renormalization group approach. Phys Rev Lett 104:025701
Tong H, Prakash BA, Tsourakakis C, Eliassi-Rad R, Faloutsos C, Chau DH (2010) On the vulnerability of large graphs. Proceedings of IEEE international conference on data mining 1091–1096
Wang C, Knight J, Elder M (2000) On computer viral infection and the effect of immunization, In proceedings of the 16th annual computer security applications conference 246–256
Yuan H, Chen G, Wu J, Xiong H (2009) Towards controlling virus propagation in information systems with point-to-group information sharing. Decis Support Syst 48:57–68