Evangelism in social networks

We consider a population of interconnected individuals that, with respect to a piece information, at each time instant can be subdivided into three (time-dependent) categories: agnostic, 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 an 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, and we present exact polynomial time algorithms for trees and complete graphs.For general graphs, we derive exact algorithms parameterized with respect to neighborhood diversity.We also study the problem when the objective is to select a minimum number of evangelists able of influencing the whole network.