@inproceedings{khanna2014influence,
author = {Khanna, Sanjeev and Lucier, Brendan},
title = {Influence Maximization in Undirected Networks},
booktitle = {Symposium on Discrete Algorithms 2014},
year = {2014},
month = {January},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/influence-maximization-undirected-networks/},
edition = {Symposium on Discrete Algorithms 2014},
}