9 - Viral marketing and optimised epidemics

Summary

Model and motivation

In Chapter 8 we tried to understand the impact of a network's topology on the behaviour of epidemics. In the present chapter, we focus on the role played by the initial condition in determining the size of the epidemic. Moreover, we adopt a different viewpoint, taking an algorithmic perspective. That is to say, we address the following question: given a set of individuals that form a network, how should one choose a subset of these individuals, of given size, to be infected initially, so as to maximise the size of an epidemic? The idea is that by carefully choosing such nodes we could trigger a cascade of infections that will result in a large number of ultimately infected individuals.

This problem finds its motivation in viral marketing. In this context, limited advertising budget is available for the purpose of convincing a small number of consumers (i.e. the size of the set of initial infectives) of the merits of some product. Such consumers may in turn convince others, and the aim is to maximise the ultimate reach of the advertisement by leveraging such “contaminations”.

We address this problem by considering the following version of the Reed–Frost epidemic. We assume that the network is described by a directed graph G. The potentially infected individuals constitute the set V ≔ {1, …, n}.