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. © 2011 IEEE.published_or_final_versionProceedings of the IEEE Global Telecommunications Conference (GLOBECOM 2011), Houston, TX, USA, 5-9 December 201