Influence diffusion in social networks under time window constraints

We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model, agents change behaviours/opinions on the basis of information collected from their neighbours in a time interval of bounded size whereas agents are assumed to have unbounded memory   in previously studied scenarios. In our mathematical framework, one is given a network G=(V,E)G=(V,E), an integer value t(v)t(v) for each node v∈Vv∈V, and a time window size λ. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node v becomes influenced if the number of its neighbours that have been influenced in the previous λ   rounds is greater than or equal to t(v)t(v). We prove that the problem of finding a minimum cardinality target set that influences the whole network G is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, and trees.