Influence Maximization in Undirected Networks

We consider the problem of finding a set of k vertices of maximal total influence in a given undirected network, under the independent cascade (IC) model of influence spread. It is known that influence is submodular in the IC model, and hence a greedy algorithm achieves a (1 – 1/e) approximation to this problem; moreover, it is known to be NP-hard to achieve a better approximation factor in directed networks. We show that for undirected networks, this approximation barrier can be overcome: the greedy algorithm obtains an (1 – 1/e + c) approximation to the set of optimal influence, for some constant c > 0. Our proof proceeds via probabilistic analysis of bond percolation in arbitrary finite networks. We also show that the influence maximization problems remains APX-hard in undirected networks.