The probabilistic maximum coverage problem in social networks

Abstract

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. © 2011 IEEE.