Time-bounded influence diffusion with incentives

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V, E) with an influence threshold t(v) for each node. Initially the members of an initial set S ⊆ V are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node v that has at least t(v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks