  The Independent Cascade Model (ICM) is a widely studied model that aims to
capture the dynamics of the information diffusion in social networks and in
general complex networks. In this model, we can distinguish between active
nodes which spread the information and inactive ones. The process starts from a
set of initially active nodes called seeds. Recursively, currently active nodes
can activate their neighbours according to a probability distribution on the
set of edges. After a certain number of these recursive cycles, a large number
of nodes might become active. The process terminates when no further node gets
activated. Starting from the work of Domingos and Richardson, several studies
have been conducted with the aim of shaping a given diffusion process so as to
maximize the number of activated nodes at the end of the process. One of the
most studied problems has been formalized by Kempe et al. and consists in
finding a set of initial seeds that maximizes the expected number of active
nodes under a budget constraint. In this paper we study a generalization of the
problem of Kempe et al. in which we are allowed to spend part of the budget to
create new edges incident to the seeds. That is, the budget can be spent to buy
seeds or edges according to a cost function. The problem does not admin a PTAS,
unless $P=NP$. We propose two approximation algorithms: the former one gives an
approximation ratio that depends on the edge costs and increases when these
costs are high; the latter algorithm gives a constant approximation guarantee
which is greater than that of the first algorithm when the edge costs can be
small.
