Minimizing Seed Set Selection with Probabilistic Coverage Guarantee in a Social Network

摘要: A topic propagating in a social network reaches its tipping point if the number of users discussing it exceeds critical threshold such that wide cascade on is likely to occur. In this paper, we consider task selecting initial seed with minimum size so guaranteed probability would reach given threshold. We formulate as an optimization problem called minimization probabilistic coverage guarantee (SM-PCG). This departs from previous studies influence maximization or because considers guarantees instead expected coverage. show not submodular, and thus harder than previously studied problems based submodular function optimization. provide approximation algorithm approximates optimal solution both multiplicative ratio additive error. The tight while error be small distributions certain sets are well concentrated. For one-way bipartite graphs analytically prove concentration condition obtain $O(\log n)$ $O(\sqrt{n})$ error, where $n$ total nodes graph. Moreover, empirically verify real-world networks experimentally demonstrate effectiveness our proposed comparing commonly adopted benchmark algorithms.