The Probabilistic Maximum Coverage Problem in Social Networks

In this paper we consider the problem of maximizing information propagation in social networks. To solve it, we introduce a probabilistic maximum coverage problem, and further purpose a cluster-based heuristic and a neighborhood-removal heuristic for two basic diffusion models, namely, the Linear Threshold Model and the Independent Cascade Model, respectively. Our proposed strategies are compared with the pure greedy algorithm and centrality-based schemes via experiments on large collaboration networks. We find that our proposed algorithms perform better than centrality-based schemes and achieve approximately the same performance as the greedy algorithm. Moreover, the computational load is significantly reduced compared with the greedy heuristic.