  We consider a population of interconnected individuals that, with respect to
a piece of information, at each time instant can be subdivided into three
(time-dependent) categories: agnostics, influenced, and evangelists. A
dynamical process of information diffusion evolves among the individuals of the
population according to the following rules. Initially, all individuals are
agnostic. Then, a set of people is chosen from the outside and convinced to
start evangelizing, i.e., to start spreading the information. When a number of
evangelists, greater than a given threshold, communicate with a node v, the
node v becomes influenced, whereas, as soon as the individual v is contacted by
a sufficiently much larger number of evangelists, it is itself converted into
an evangelist and consequently it starts spreading the information. The
question is: How to choose a bounded cardinality initial set of evangelists so
as to maximize the final number of influenced individuals? We prove that the
problem is hard to solve, even in an approximate sense. On the positive side,
we present exact polynomial time algorithms for trees and complete graphs. For
general graphs, we derive exact parameterized algorithms. We also investigate
the problem when the objective is to select a minimum number of evangelists
capable of influencing the whole network. Our motivations to study these
problems come from the areas of Viral Marketing and the analysis of
quantitative models of spreading of influence in social networks.
