Optimizing Spread of Influence in Social Networks via Partial Incentives

A widely studied process of influence diffusion in social networks posits that the dynamics of influence diffusion evolves as follows: Given a graph

G

 = (

V

,

E

), representing the network, initially

only

the members of a given

S

 ⊆ 

V

are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The general problem is to find a small initial set of nodes that influences the whole network. In this paper we extend the previously described basic model in the following ways: firstly, we assume that there are non negative values

c

(

v

) associated to each node

v

 ∈ 

V

, measuring how much it costs to initially influence node

v

, and the algorithmic problem is to find a set of nodes of

minimum total cost

that influences the whole network; successively, we study the consequences of giving

incentives

to member of the networks, and we quantify how this affects (i.e., reduces) the total costs of starting an influence diffusion process that influence the whole network. For the two above problems we provide both hardness results and algorithms. We also experimentally validate our algorithms via extensive simulations on real life networks.