Evaluation of Epidemic Seeding Strategies under Variable Node Costs - Chiesse, Ronald; Figueiredo, Daniel; Rocha, Antonio; Ziviani, Arthur (Anais do Workshop em Desempenho de Sistemas Computacionais e de Comunicação (WPerformance); 2014: Anais do XIII Workshop em Desempenho de Sistemas Computacionais e de Comunicação, 2014)
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.