ABSTRACT
Suppose we have a virus or one competing idea/product that propagates over a multiple profile (e.g., social) network. Can we predict what proportion of the network will actually get "infected" (e.g., spread the idea or buy the competing product), when the nodes of the network appear to have different sensitivity based on their profile? For example, if there are two profiles A and B in a network and the nodes of profile A and profile B are susceptible to a highly spreading virus with probabilities βA and βB respectively, what percentage of both profiles will actually get infected from the virus at the end? To reverse the question, what are the necessary conditions so that a predefined percentage of the network is infected? We assume that nodes of different profiles can infect one another and we prove that under realistic conditions, apart from the weak profile (great sensitivity), the stronger profile (low sensitivity) will get infected as well. First, we focus on cliques with the goal to provide exact theoretical results as well as to get some intuition as to how a virus affects such a multiple profile network. Then, we move to the theoretical analysis of arbitrary networks. We provide bounds on certain properties of the network based on the probabilities of infection of each node in it when it reaches the steady state. Finally, we provide extensive experimental results that verify our theoretical results and at the same time provide more insight on the problem.
Supplemental Material
- R. M. Anderson and R. M. May". "Infectious Diseases of Humans". "Oxford University Press", "1991".Google Scholar
- S. Aral and D. Walker. Identifying influential and susceptible members of social networks. Science, 337, 2012.Google ScholarCross Ref
- N. Bailey". "The Mathematical Theory of Infectious Diseases and its Applications". "Griffin", "London", "1975".Google Scholar
- N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. In 12th IEEE International Conference on Data Mining, ICDM 2012, Brussels, Belgium, December 10-13, 2012, pages 81--90, 2012. Google ScholarDigital Library
- A. Beutel, B. A. Prakash, R. Rosenfeld, and C. Faloutsos. Interacting viruses in networks: Can both survive? In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '12, pages 426--434, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
- B. Chazelle. Analytical tools for natural algorithms. In A. C.-C. Yao, editor, ICS, pages 32--41. Tsinghua University Press, 2010.Google Scholar
- P. Domingos and M. Richardson. Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '01, pages 57--66, New York, NY, USA, 2001. ACM Press. Google ScholarDigital Library
- A. Ganesh, L. Massoulie, and D. Towsley. The effect of network topology on the spread of epidemics. In INFOCOM, 2005.Google ScholarCross Ref
- H. Gould and J. Tobochnik. Statistical and Thermal Physics: With Computer Applications. Princeton University Press, 2010. Google ScholarDigital Library
- M. Granovetter. Threshold models of collective behavior. Am. Journal of Sociology, 6(83):1420--1443, 1978.Google Scholar
- H. W. Hethcote. The mathematics of infectious diseases. SIAM Rev., 42(4):599--653, Dec. 2000. Google ScholarDigital Library
- M. W. Hirsch and S. Smale". "Differential Equations, Dynamical Systems and Linear Algebra". "Academic Press", "1974".Google Scholar
- D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- J. O. Kephart and S. R. White. Measuring and modeling computer virus prevalence. In IEEE Computer Society Symposium on Research in Security and Privacy, 1993. Google ScholarDigital Library
- M. Kimura, K. Saito, and H. Motoda. Efficient estimation of influence functions for SIS model on social networks. In IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pages 2046--2051, 2009. Google ScholarDigital Library
- J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29--123, 2009.Google ScholarCross Ref
- E. S. G. Lum Kristian, Swarup Samarth and H. James. The contagious nature of imprisonment: An agent-based model to explain racial disparities in incarceration rates. J. R. Soc. Interface, 11(98):201404090, June 2014.Google Scholar
- A. G. McKendrick. Applications of mathematics to medical problems. In Proceedings of Edin. Math. Society, volume 14, pages 98--130, 2011.Google Scholar
- R. Pastor-Santorras and A. Vespignani. Epidemic spreading in scale-free networks. Physical Review Letters, 86(14), 2001.Google Scholar
- B. A. Prakash, A. Beutel, R. Rosenfeld, and C. Faloutsos. Winner takes all: Competing viruses or ideas on fair-play networks. In Proceedings of the 21st International Conference on World Wide Web, WWW '12, pages 1037--1046, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
- B. A. Prakash, D. Chakrabarti, M. Faloutsos, N. Valler, and C. Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. In Proceedings of the 2011 IEEE 11th International Conference on Data Mining, ICDM '11, pages 537--546, Washington, DC, USA, 2011. IEEE Computer Society. Google ScholarDigital Library
- K. Saito, M. Kimura, and H. Motoda. Discovering influential nodes for SIS models in social networks. In Discovery Science, 12th International Conference, DS 2009, Porto, Portugal, October 3-5, 2009, pages 302--316, 2009. Google ScholarDigital Library
- X. Wei, N. Valler, B. A. Prakash, I. Neamtiu, M. Faloutsos, and C. Faloutsos. Competing memes propagation on networks: A case study of composite networks. IEEE Journal on Selected Areas in Communications, 6(31):1049--1060, 2013.Google ScholarCross Ref
Index Terms
- Virus Propagation in Multiple Profile Networks
Recommendations
Node centrality analysis of multiplex networks under Computer virus spreading
Computer virus is evolving by developing spreading mechanisms based on the use of multiple vectors of propagation. Finding important nodes in the network and taking action can effectively control the range and speed of the computer virus. Most of the ...
Comments