Wei Chen
Tian Lin
ABSTRACT
In 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 propose the problem of robust influence maximization, which maximizes the worst-case ratio between the influence spread of the chosen seed set and the optimal seed set, given the uncertainty of the parameter input. We design an algorithm that solves this problem with a solution-dependent bound. We further study uniform sampling and adaptive sampling methods to effectively reduce the uncertainty on parameters and improve the robustness of the influence maximization task. Our empirical results show that parameter uncertainty may greatly affect influence maximization performance and prior studies that learned influence probabilities could lead to poor performance in robust influence maximization due to relatively large uncertainty in parameter estimates, and information cascade based adaptive sampling method may be an effective way to improve the robustness of influence maximization.
Supplemental Material
- A. Badanidiyuru, R. Kleinberg, and A. Slivkins. Bandits with knapsacks. In FOCS 2013. Google Scholar
Digital Library
- N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. Knowledge and information systems, 37(3):555--584, 2013.Google Scholar
- A. Ben-Tal and A. Nemirovski. Robust optimization--methodology and applications. Mathematical Programming, 92(3):453--480, 2002.Google ScholarCross Ref
- C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA 2014. Google ScholarDigital Library
- S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 412:1832--1852, 2011. Google ScholarDigital Library
- C. Budak, D. Agrawal, and A. El Abbadi. Limiting the spread of misinformation in social networks. In WWW 2011. Google ScholarDigital Library
- S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. Combinatorial pure exploration of multi-armed bandits. In NIPS 2014. Google ScholarDigital Library
- W. Chen, L. V. Lakshmanan, and C. Castillo. Information and influence propagation in social networks. Synthesis Lectures on Data Management, 5(4):1--177, 2013. Google ScholarCross Ref
- W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou. Robust influence maximization. CoRR, abs/1601.06551, 2016. Google ScholarDigital Library
- 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 and its extension to probabilistically triggered arms. CoRR, abs/1407.8339, 2014.Google Scholar
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD 2001. Google ScholarDigital Library
- U. Feige. A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634--652, 1998. 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, W. Lu, and L. V. Lakshmanan. Celf+: optimizing the greedy algorithm for influence maximization in social networks. In WWW 2011. Google ScholarDigital Library
- X. He and D. Kempe. Robust influence maximization. In KDD 2016. Google ScholarDigital Library
- X. He and D. Kempe. Stability of Influence Maximization. ArXiv e-prints, Jan. 2015.Google Scholar
- D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD 2003. Google ScholarDigital Library
- A. Krause, H. B. McMahon, C. Guestrin, and A. Gupta. Robust submodular observation selection. JMLR, 9:2761--2801, 2008.Google Scholar
- S. Lei, S. Maniu, L. Mo, R. Cheng, and P. Senellart. Online influence maximization. In KDD 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
- W. Lu, W. Chen, and L. V. Lakshmanan. From competition to complementarity: comparative influence diffusion and maximization. In VLDB 2015. Google ScholarDigital Library
- P. Netrapalli and S. Sanghavi. Learning the graph of epidemic cascades. In SIGMETRICS 2012. Google ScholarDigital Library
- M. G. Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffusion networks. In ICML 2011.Google Scholar
- K. Saito, R. Nakano, and M. Kimura. Prediction of information diffusion probabilities for independent cascade model. In Knowledge-Based Intelligent Information and Engineering Systems, pages 67--75. Springer, 2008. Google ScholarDigital Library
- J. Tang, J. Sun, C. Wang, and Z. Yang. Social influence analysis in large-scale networks. In KDD 2009. 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
Index Terms
- Robust Influence Maximization
Recommendations
Stability and Robustness in Influence Maximization
In the well-studied Influence Maximization problem, the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. A large body of recent work has justified research on Influence Maximization models and ...
Robust Influence Maximization
KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data MiningUncertainty about models and data is ubiquitous in the computational social sciences, and it creates a need for robust social network algorithms, which can simultaneously provide guarantees across a spectrum of models and parameter settings. We begin an ...
An Exact Algorithm for Robust Influence Maximization
Integer Programming and Combinatorial OptimizationAbstractWe propose a Branch-and-Cut algorithm for the robust influence maximization problem. The influence maximization problem aims to identify, in a social network, a set of given cardinality comprising actors that are able to influence the maximum ...
Comments