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 behaviors/opinions on the basis of information collected from their neighbors 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

), an integer value

t

(

v

) for each node

v

 ∈ 

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 neighbors that have been influenced in the previous

λ

rounds is greater than or equal to

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, trees, and complete graphs.