Evaluation of Epidemic Seeding Strategies under Variable Node Costs
Resumo
Network epidemics is a general modeling framework useful to represent dynamic processes over networks, such as the spread of a virus on a computer network or information dissemination on a social network. Within this framework, network seeding is the problem of determining which network nodes should be selected to start an epidemic. Intuitively, the success of an epidemic under some performance metric (ex. number of reached nodes) largely depends on the set of initially infected nodes. Prior approaches to effective network seeding have treated nodes identically in terms of their respective cost to start an epidemic. However, we argue that such assumption is inadequate in many cases and thus consider network seeding under variable node cost. We propose a degree-based cost function and evaluate the performance of four different network seeding strategies over two different network models. Our results show that no seeding strategy is consistently superior under identical budgets. In particular, we identify a tradeoff between strategies that select (hire) a larger number of cheap nodes (low degree) and strategies that select few expensive nodes (high degree). Our results shed light on the importance of taking into account variable node cost, a more realistic assumption in many applications.
Referências
Arthur, D., Motwani, R., Sharma, A., and Xu, Y. (2009). Pricing strategies for viral marketing on social networks. In Internet and Network Economics, volume 5929 of Lecture Notes in Computer Science, pages 101–112.
Cha, M., Haddadi, H., Benevenuto, F., and Gummadi, K. P. (2010). Measuring user inuence in twitter: The million follower fallacy. In International AAAI Conference on Weblogs and Social Media (ICWSM), pages 10–17.
Chen, W., Wang, Y., and Yang, S. (2009). Efcient inuence maximization in social networks. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 199–208.
Figueiredo, D. R. (2011). Introdução a redes complexas. Atualizações em Informática, chapter 7, pages 303–358. PUC-Rio.
Hinz, O., Skiera, B., Barrot, C., and Becker, J. U. (2011). Seeding strategies for viral marketing: An empirical comparison. Journal of Marketing, 75:55–71.
Kempe, D., Kleinberg, J., and Tardos, E. (2003). Maximizing the spread of inuence through a social network. In ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 137–146.
Kitsak, M., Gallos, L. K., Havlin, S., Liljeros, F., Muchnik, L., Stanley, H. E., and Makse, Identication of inuential spreaders in complex networks. Nature H. A. (2010). Physics, 6:888–893.
Kornowski, L. (2013). Celebrity sponsored tweets: What the stars get paid for advertising in 140 characters. The Hufngton Post.
Kostka, J., Oswald, Y., and Wattenhofer, R. (2008). Word of mouth: Rumor dissemination in social networks. In Structural Information and Communication Complexity, volume 5058 of Lecture Notes in Computer Science, pages 185–196.
Leskovec, J., Adamic, L. A., and Huberman, B. A. (2007). The dynamics of viral marketing. ACM Trans. Web, 1(1).
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
