Active influence spreading in social networks

Identifying the most influential spreaders is an important issue for the study of the dynamics of information diffusion in complex networks. In this paper we analyze the following spreading model. Initially, a few nodes know a piece of information and are active spreaders of it. At subsequent rounds, spreaders communicate the information to their neighbors. Upon receiving the information, a node becomes aware of it but does not necessarily become a spreader; it starts spreading only if it gets the information from a sufficiently large number of its neighbors. A set of initial spreaders that guarantees that all the nodes become aware of the information is called a perfect seed set. We study the problem of choosing a perfect seed set of minimum size. We provide hardness results and show that the problem becomes tractable on trees. In case of general graphs, we provide an efficient algorithm and validate its effectiveness (in terms of the solution size) on real-life networks. We also study perfect seed sets in dense graphs and derive a bound on the size of a dominating set in Ore graphs.