|
Abstract |
A topic propagating in a social network reaches its tipping point if the number of users discussing it in the network exceeds a critical threshold such that a wide cascade on the topic is likely to occur. In this paper, we consider the task of selecting initial seed users of a topic with minimum size so that with a guaranteed probability the number of users discussing the topic would reach a given threshold. This problem departs from the previous studies on social influence maximization or seed minimization because it considers influence coverage with probabilistic guarantees instead of guarantees on expected influence coverage. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. Moreover, we empirically verify the concentration condition in real-world networks and experimentally demonstrate the effectiveness of our proposed algorithm comparing to commonly adopted benchmark algorithms. |
