Minimizing seed set selection with probabilistic coverage guarantee in a social network

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 {\em with a guaranteed probability} the number of users discussing the topic would reach a given threshold. We formulate the task as an optimization problem called {\em seed minimization with probabilistic coverage guarantee (SM-PCG)}. This problem departs from the previous studies on social influence maximization or seed minimization because it considers influence coverage with {\em probabilistic} guarantees instead of guarantees on {\em expected} influence coverage. We show that the problem is not submodular, and thus is harder than previously studied problems based on submodular function optimization. We provide an approximation algorithm and show that it approximates the optimal solution with both a multiplicative ratio and an additive error. The multiplicative ratio is tight while the additive error would be small if influence coverage distributions of certain seed sets are well concentrated. For one-way bipartite graphs we analytically prove the concentration condition and obtain an approximation algorithm with an $O(\log n)$ multiplicative ratio and an $O(\sqrt{n})$ additive error, where $n$ is the total number of nodes in the social graph. 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.

References

1. N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 81--90. IEEE, 2012.
2. S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1):107--117, 1998.
3. N. Chen. On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics, 23(3):1400--1415, 2009.
4. W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD'10, pages 1029--1038. ACM, 2010.
5. W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD'09, pages 199--208, 2009.
6. W. Chen, Y. Yuan, and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In ICDM'10, pages 88--97, 2010.
7. P. Domingos and M. Richardson. Mining the network value of customers. In KDD'01, pages 57--66. ACM, 2001.
8. N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Advances in Neural Information Processing Systems, pages 3147--3155, 2013.
9. U. Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634--652, 1998.
10. M. Gladwell. The Tipping Point:How Little Things Can Make a Big Difference. Back Bay Books, 2002.
11. S. Goldberg and Z. Liu. The Diffusion of Networking Technologies. In SODA'13, pages 1577--1594, 2013.
12. A. Goyal, F. Bonchi, L. V. Lakshmanan, and S. Venkatasubramanian. On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining, pages 1--14, 2012.
13. A. Goyal, W. Lu, and L. V. S. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In ICDM'11, pages 211--220, 2011.
14. D. Kempe, J. Kleinberg, and --E. Tardos. Maximizing the spread of influence through a social network. In KDD'03, pages 137--146. ACM, 2003.
15. J. Leskovec. Wiki-vote social network. http://snap.stanford.edu/data/wiki-Vote.html.
16. C. Long and R.-W. Wong. Minimizing seed set for viral marketing. In Data Mining (ICDM), 2011 IEEE 11th International Conference on, pages 427--436. IEEE, 2011.
17. M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD'02, pages 61--70. ACM, 2002.
18. M. G. Rodriguez and B. Schölkopf. Influence maximization in continuous time diffusion networks. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), pages 313--320, 2012.
19. L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410--421, 1979.
20. P. Zhang, W. Chen, X. Sun, Y. Wang, and J. Zhang. Minimizing seed set selection with probabilistic coverage guarantee in a social network. arXiv preprint arXiv:1402.5516, 2014.

Index Terms

• Information systems

  • Information systems applications