Siyu Lei
Pierre Senellart
ABSTRACT
Social networks are commonly used for marketing purposes. For example, free samples of a product can be given to a few influential social network users (or seed nodes), with the hope that they will convince their friends to buy it. One way to formalize this objective is through the problem of influence maximization (or IM), whose goal is to find the best seed nodes to activate under a fixed budget, so that the number of people who get influenced in the end is maximized. Solutions to IM rely on the influence probability that a user influences another one. However, this probability information may be unavailable or incomplete. In this paper, we study IM in the absence of complete information on influence probability. We call this problem Online Influence Maximization (OIM), since we learn influence probabilities at the same time we run influence campaigns. To solve OIM, we propose a multiple-trial approach, where (1) some seed nodes are selected based on existing influence information; (2) an influence campaign is started with these seed nodes; and (3) user feedback is used to update influence information. We adopt Explore-Exploit strategies, which can select seed nodes using either the current influence probability estimation (exploit), or the confidence bound on the estimation (explore). Any existing IM algorithm can be used in this framework. We also develop an incremental algorithm that can significantly reduce the overhead of handling user feedback information. Our experiments show that our solution is more effective than traditional IM methods on the partial information.
Supplemental Material
- S. Agrawal and N. Goyal. Analysis of thompson sampling for the multi-armed bandit problem. In COLT, 2012.Google Scholar
- C. Aslay, N. Barbieri, F. Bonchi, and R. A. Baeza-Yates. Online topic-aware influence maximization queries. In EDBT, 2014.Google Scholar
- P. Auer. Using confidence bounds for exploitation-exploration trade-offs. JMLR, 3:397--422, 2003. Google ScholarDigital Library
- C. Borgs, M. Bratbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, 2014. Google ScholarDigital Library
- N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006. Google ScholarCross Ref
- W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD, 2010. Google ScholarDigital Library
- W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, 2009. Google ScholarDigital Library
- W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In ICML, 2013.Google ScholarDigital Library
- W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, 2010. Google ScholarDigital Library
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, 2001. Google ScholarDigital Library
- A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning influence probabilities in social networks. In WSDM, 2010. Google ScholarDigital Library
- A. Goyal, F. Bonchi, and L. V. Lakshmanan. A data-based approach to social influence maximization. PVLDB, 5(1), 2011. Google ScholarDigital Library
- A. Goyal, W. Lu, and L. V. Lakshmanan. CelfGoogle Scholar
- : Optimizing the greedy algorithm for influence maximization in social networks. In WWW, 2011. Google ScholarDigital Library
- J. Huang, X.-Q. Cheng, H.-W. Shen, T. Zhou, and X. Jin. Exploring social influence via posterior effect of word-of-mouth recommendations. In WSDM, 2012. Google ScholarDigital Library
- K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In ICDM, 2012. Google ScholarDigital Library
- D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, 2003. Google ScholarDigital Library
- J. Kim, S.-K. Kim, and H. Yu. Scalable and parallelizable processing of influence maximization for large-scale social networks? In ICDE, 2013.Google Scholar
- S. Lei, S. Maniu, L. Mo, R. Cheng, and P. Senellart. Online influence maximization (extended version). arXiv:1056.01188, 2015. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, 2007. Google ScholarDigital Library
- M. J. Lovett, R. Peres, and R. Shachar. On brands and word of mouth. J. Marketing Research, 50(4), 2013.Google ScholarCross Ref
- W. Lu, F. Bonchi, A. Goyal, and L. V. Lakshmanan. The bang for the buck: Fair competitive viral marketing from the host perspective. KDD, 2013. Google ScholarDigital Library
- S. Richard and A. Barto. Reinforcement Learning: An Introduction. MIT Press, 1998.Google Scholar
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD 2002. Google ScholarDigital Library
- H. Robbins. Some aspects of the sequential design of experiments. Bull. Amer. Math. Soc., 58(5), 1952.Google Scholar
- K. Saito, R. Nakano, and M. Kimura. Prediction of information diffusion probabilities for independent cascade model. In KES, 2008. Google ScholarDigital Library
- Y. Singer. How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In WSDM, 2012. Google ScholarDigital Library
- Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD, 2014. Google ScholarDigital Library
- Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In KDD, 2010. Google ScholarDigital Library
Index Terms
- Online Influence Maximization
Recommendations
Efficient influence maximization in social networks
KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data miningInfluence maximization is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. In this paper, we study the efficient influence maximization from two complementary directions. One is ...
Robust Influence Maximization
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data MiningIn this paper, we address the important issue of uncertainty in the edge influence probability estimates for the well studied influence maximization problem --- the task of finding k seed nodes in a social network to maximize the influence spread. We ...
Maximizing the spread of influence through a social network
KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data miningModels for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies ...
Comments