Xinran He
ABSTRACT
Uncertainty 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 investigation into this broad domain by studying robust algorithms for the Influence Maximization problem, in which the goal is to identify a set of k nodes in a social network whose joint influence on the network is maximized. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions, typically derived from different influence models or different parameter settings for the same model. The different parameter settings could be derived from observed cascades on different topics, under different conditions, or at different times. The algorithm's goal is to identify a set of k nodes who are simultaneously influential for all influence functions, compared to the (function-specific) optimum solutions.
We show strong approximation hardness results for this problem unless the algorithm gets to select at least a logarithmic factor more seeds than the optimum solution. However, when enough extra seeds may be selected, we show that techniques of Krause et al. can be used to approximate the optimum robust influence to within a factor of 1-1/e. We evaluate this bicriteria approximation algorithm against natural heuristics on several real-world data sets. Our experiments indicate that the worst-case hardness does not necessarily translate into bad performance on real-world data sets; all algorithms perform fairly well.
Supplemental Material
- B. Abrahao, F. Chierichetti, R. Kleinberg, and A. Panconesi. Trace complexity of network inference. In Proc. 19th KDD, pages 491--499, 2013. Google Scholar
Digital Library
- A. Adiga, C. J. Kuhlman, H. S. Mortveit, and A. K. S. Vullikanti. Sensitivity of diffusion dynamics to network uncertainty. In Proc. 28th AAAI, 2013. Google ScholarDigital Library
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In Proc. 25th ACM SODA, pages 946--957, 2014. Google ScholarDigital Library
- K. E. Campbell and B. A. Lee. Name generators in surveys of personal networks. Social Networks, 13(3):203--221, 1991.Google ScholarCross Ref
- W. Chen, L. V. Lakshmanan, and C. Castillo. Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool, 2013. Google ScholarDigital Library
- W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou. Robust influence maximization. In Proc. 22nd KDD, 2016. Google ScholarDigital Library
- W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proc. 15th KDD, pages 199--208, 2009. Google ScholarDigital Library
- W. Chen, Y. Wang, Y. Yuan, and Q. Wang. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. J. Mach. Learn. Res., 17(1):1746--1778, 2016. Google ScholarDigital Library
- W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In Proc. 10th ICDM, pages 88--97, 2010. Google ScholarDigital Library
- X. Chen, G. Song, X. He, and K. Xie. On influential nodes tracking in dynamic social networks. In Proc. 15th SDM, pages 613--621, 2015.Google ScholarCross Ref
- H. Daneshmand, M. Gomez-Rodriguez, L. Song, and B. Schölkopf. Estimating diffusion network structures: Recovery conditions, sample complexity & soft-thresholding algorithm. In Proc. 31st ICML, 2014.Google Scholar
- N. Du, Y. Liang, M.-F. Balcan, and L. Song. Influence function learning in information diffusion networks. In Proc. 31st ICML, 2014.Google Scholar
- N. Du, L. Song, M. Gomez-Rodriguez, and H. Zha. Scalable influence estimation in continuous-time diffusion networks. In Proc. 25th NIPS, 2013.Google Scholar
- M. Gomez-Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffusion networks. In Proc. 28th ICML, pages 561--568, 2011.Google ScholarDigital Library
- M. Gomez-Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4):21, 2012. Google ScholarDigital Library
- M. Gomez-Rodriguez and B. Schölkopf. Submodular inference of diffusion networks from multiple trees. In Proc. 29th ICML, 2012.Google Scholar
- A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A data-based approach to social influence maximization. Proc. VLDB Endowment, 5(1):73--84, 2011. Google ScholarDigital Library
- A. Goyal, F. Bonchi, L. V. S. Lakshmanan, and S. Venkatasubramanian. On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining, 3(2):179--192, 2013.Google ScholarCross Ref
- X. He and D. Kempe. Stability of influence maximization. Unpublished Manuscript, available at http://arxiv.org/abs/1501.04579, 2015. Google ScholarDigital Library
- X. He and D. Kempe. Robust influence maximization. Technical Report, http://arxiv.org/abs/1602.05240, 2016.Google Scholar
- D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence in a social network. Theory of Computing, 11(4):105--147, 2015. A preliminary version of the results appeared in KDD 2003 and ICALP 2005. Google ScholarDigital Library
- S. Khanna and B. Lucier. Influence maximization in undirected networks. In Proc. 25th ACM SODA, pages 1482--1496, 2014. Google ScholarDigital Library
- A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. In Journal of Machine Learning Research, volume 9, pages 2761--2801, 2008.Google Scholar
- S. Lei, S. Maniu, L. Mo, R. Cheng, and P. Senellart. Online influence maximization. In Proc. 21st KDD, pages 645--654, 2015. Google ScholarDigital Library
- J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. In Proc. 15th KDD, pages 497--506, 2009. Note: updated data sets at http://www.memetracker.org/. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In Proc. 13th KDD, pages 420--429, 2007. Google ScholarDigital Library
- M. Lowalekar, P. Varakantham, and A. Kumar. Robust influence maximization (extended abstract). In Proc. 15th AAMAS, pages 1395--1396, 2016. Google ScholarDigital Library
- E. Mossel and S. Roch. Submodularity of influence in social networks: From local to global. SIAM J. Comput., 39(6):2176--2188, 2010.Google ScholarCross Ref
- S. A. Myers and J. Leskovec. On the convexity of latent social network inference. In Proc. 22nd NIPS, pages 1741--1749, 2010.Google ScholarDigital Library
- H. Narasimhan, D. C. Parkes, and Y. Singer. Learnability of influence in networks. In Proc. 27th NIPS, pages 3168--3176, 2015. Google ScholarDigital Library
- G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.Google ScholarDigital Library
- P. Netrapalli and S. Sanghavi. Learning the graph of epidemic cascades. In ACM SIGMETRICS Performance Evaluation Review, pages 211--222, 2012. Google ScholarDigital Library
- K. Saito, M. Kimura, K. Ohara, and H. Motoda. Selecting information diffusion models over social networks for behavioral analysis. In Proc. 2010 European Conference on Machine Learning and Knowledge Discovery in Databases: Part III, ECML/PKDD 10, pages 180--195, 2010. Google ScholarDigital Library
- C. Wang, W. Chen, and Y. Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery Journal, 25(3):545--576, 2012.Google ScholarCross Ref
- Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proc. 16th KDD, pages 1039--1048, 2010. Google ScholarDigital Library
Index Terms
- Robust Influence Maximization
Recommendations
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 ...
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 ...
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