Document Type
Article
Publication Date
11-10-2025
Publisher
Association for Computing Machinery
Abstract
The influence estimation and maximization problems study the expected reach of a seed set in social networks under a stochastic propagation model. Motivated by the practical utility of characterizing the distribution of reach values, we systematically analyze the tail behaviour of the reach of a seed set. We study tail bound query problems that, for a given seed set, compute either the maximum reach for a given probability threshold or the highest probability of achieving a target reach. We prove #P-hardness and propose algorithms that balance efficiency and accuracy. We also examine tail bound optimization problems that find a seed set maximizing reach for a target probability or maximizing the probability of achieving a target reach, and establish strong inapproximability results.
Experiments on real datasets demonstrate the effectiveness of our algorithms, showing that good approximations of the actual reach for a desired probability can be computed efficiently and that the actual reach can be very different from the expected reach.
Recommended Citation
Simpson, M., V. S. Lakshmanan, L., Srinivasan, V., & Thomo, A. (2025). On Influence Tail Bounds in Online Social Networks. Proceedings of the 34th ACM International Conference on Information and Knowledge Management, CIKM ’25, 5253–5257. https://doi.org/10.1145/3746252.3760910
Comments
Open access to this article is funded by Santa Clara University Library.
This work is licensed under a Creative Commons Attribution International 4.0 License.