Abstract
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 algorithms with their potential to create societal or economic value. However, in order to live up to this potential, the algorithms must be robust to large amounts of noise, for they require quantitative estimates of the influence, which individuals exert on each other; ground truth for such quantities is inaccessible, and even decent estimates are very difficult to obtain.
We begin to address this concern formally. First, we exhibit simple inputs on which even very small estimation errors may mislead every algorithm into highly suboptimal solutions. Motivated by this observation, we propose the Perturbation Interval model as a framework to characterize the stability of Influence Maximization against noise in the inferred diffusion network. Analyzing the susceptibility of specific instances to estimation errors leads to a clean algorithmic question, which we term the Influence Difference Maximization problem. However, the objective function of Influence Difference Maximization is NP-hard to approximate within a factor of O(n1−ϵ) for any ϵ > 0.
Given the infeasibility of diagnosing instability algorithmically, we focus on finding influential users robustly across multiple diffusion settings. We define a Robust Influence Maximization framework wherein an algorithm is presented with a set of influence functions. 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 datasets. Our experiments indicate that the worst-case hardness does not necessarily translate into bad performance on real-world datasets; all algorithms perform fairly well.
- Bruno Abrahao, Flavio Chierichetti, Robert Kleinberg, and Alessandro Panconesi. 2013. Trace complexity of network inference. In Proc. 19th KDD. 491--499. Google ScholarDigital Library
- Abhijin Adiga, Chris J. Kuhlman, Henning S. Mortveit, and Anil Kumar S. Vullikanti. 2013. Sensitivity of diffusion dynamics to network uncertainty. In Proc. 28th AAAI. Google ScholarDigital Library
- Noga Alon, Itai Benjamini, and Alan Stacey. 2004. Percolation on finite graphs and isoperimetric inequalities. Annals of Probability 32 (2004), 1727--1745.Google ScholarCross Ref
- Eric Balkanski, Nicole Immorlica, and Yaron Singer. 2017. The importance of communities for learning to influence. In Proc. 29th NIPS. 5864--5873.Google Scholar
- Eric Balkanski, Aviad Rubinstein, and Yaron Singer. 2016. The power of optimization from samples. In Proc. 28th NIPS. 4017--4025. Google ScholarDigital Library
- Eric Balkanski, Aviad Rubinstein, and Yaron Singer. 2017. The limitations of optimization from samples. In Proc. 49th ACM STOC. 1016--1027. Google ScholarDigital Library
- Noam Berger, Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Degree distribution of the FKP network model. In Proc. 30th ICALP. 725--738. Google ScholarDigital Library
- Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. 2014. Maximizing social influence in nearly optimal time. In Proc. 25th ACM SODA. 946--957. Google ScholarDigital Library
- Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. 2014. Submodular maximization with cardinality constraints. In Proc. 25th ACM SODA. 1433--1452. Google ScholarDigital Library
- Karen E. Campbell and Barrett A. Lee. 1991. Name generators in surveys of personal networks. Social Networks 13, 3 (1991), 203--221.Google ScholarCross Ref
- Robert S. Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. 2017. Robust optimization for non-convex objectives. In Proc. 29th NIPS. 4708--4717.Google Scholar
- Wei Chen, Laks V. S. Lakshmanan, and Carlos Castillo. 2013. Information and Influence Propagation in Social Networks. Morgan 8 Claypool. Google ScholarDigital Library
- Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, and Xuren Zhou. 2016. Robust influence maximization. In Proc. 22nd KDD. 795--804. Google ScholarDigital Library
- Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proc. 15th KDD. 199--208. Google ScholarDigital Library
- Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. 2016. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms. Journal of Machine Learning Research 17, 50 (2016), 1--33. Google ScholarDigital Library
- Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In Proc. 10th ICDM. 88--97. Google ScholarDigital Library
- Irit Dinur and David Steurer. 2014. Analytical approach to parallel repetition. In Proc. 46th ACM STOC. 624--633. Google ScholarDigital Library
- Pedro Domingos and Matthew Richardson. 2001. Mining the network value of customers. In Proc. 7th KDD. 57--66. Google ScholarDigital Library
- Nan Du, Yingyu Liang, Maria-Florina Balcan, and Le Song. 2014. Influence function learning in information diffusion networks. In Proc. 31st ICML. 2016--2024. Google ScholarDigital Library
- Nan Du, Le Song, Manuel Gomez-Rodriguez, and Hongyuan Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. In Proc. 25th NIPS. 3147--3155. Google ScholarDigital Library
- Paul Erdős and Alfréd Rényi. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1 (1960), 17--60.Google Scholar
- Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters 12, 3 (2001), 211--223.Google ScholarCross Ref
- Jacob Goldenberg, Barak Libai, and Eitan Muller. 2001. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review 2001 (2001), 1--18.Google Scholar
- Manuel Gomez-Rodriguez, David Balduzzi, and Bernhard Schölkopf. 2011. Uncovering the temporal dynamics of diffusion networks. In Proc. 28th ICML. 561--568. Google ScholarDigital Library
- Manuel Gomez-Rodriguez, Jure Leskovec, and Andrease Krause. 2012. Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data 5, 4 (2012), 21:1--21:37. Google ScholarDigital Library
- Manuel Gomez-Rodriguez and Bernhard Schölkopf. 2012. Submodular inference of diffusion networks from multiple trees. In Proc. 29th ICML. Google ScholarDigital Library
- Manuel Gomez-Rodriguez, Le Song, Hadi Daneshmand, and B. Schölkopf. 2014. Estimating diffusion network structures: Recovery conditions, sample complexity 8 soft-thresholding algorithm. In Proc. 31st ICML. 793--801. Google ScholarDigital Library
- Amit Goyal, Francesco Bonchi, Laks V. S. Lakshmanan, and Suresh Venkatasubramanian. 2013. On minimizing budget and time in influence propagation over social networks. Social Network Analysis and Mining 3, 2 (2013), 179--192.Google ScholarCross Ref
- Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan. 2011. A data-based approach to social influence maximization. In Proc. VLDB Endowment. 5, 1 (sep 2011), 73--84. Google ScholarDigital Library
- Mark Granovetter. 1978. Threshold models of collective behavior. American Journal of Sociology 83 (1978), 1420--1443.Google ScholarCross Ref
- Avinatan Hassidim and Yaron Singer. 2016. Submodular optimization under noise. In Proc. 30th COLT. 1069--1122.Google Scholar
- Johan Håstad. 1999. Clique is hard to approximate within n<sup>1-ϵ</sup> . Acta Mathematica 182 (1999), 105--142.Google ScholarCross Ref
- Xinran He and David Kempe. 2016. Robust influence maximization. In Proc. 22nd KDD. 885--894. Google ScholarDigital Library
- David Kempe, Jon Kleinberg, and Éva Tardos. 2015. Maximizing the spread of influence through a social network.Theory of Computing 11, 4 (2015), 105--147.Google Scholar
- Harry Kesten. 1990. Asymptotics in high dimension for percolation. In Disorder in Physical System, Geoffrey Grimmett and Dominic Welsh (Eds.). Oxford University Press, 219--240.Google Scholar
- Sanjeev Khanna and Brendan Lucier. 2014. Influence maximization in undirected networks. In Proc. 25th ACM SODA. 1482--1496. Google ScholarDigital Library
- Andreas Krause, H. Brendan McMahan, Carlos Guestrin, and Aunpam Gupta. 2008. Robust submodular observation selection. Journal of Machine Learning Research 9 (2008), 2761--2801.Google Scholar
- Siyu Lei, Silviu Maniu, Luyi Mo, Reynold Cheng, and Pierre Senellart. 2015. Online influence maximization. In Proc. 21st KDD. 645--654. Google ScholarDigital Library
- Jure Leskovec, Lars Backstrom, and Jon Kleinberg. 2009. Meme-tracking and the dynamics of the news cycle. In Proc. 15th KDD. 497--506. Google ScholarDigital Library
- Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11 (2010), 985--1042. Google ScholarDigital Library
- Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie S. Glance. 2007. Cost-effective outbreak detection in networks. In Proc. 13th KDD. 420--429. Google ScholarDigital Library
- Meghna Lowalekar, Pradeep Varakantham, and Akshat Kumar. 2016. Robust influence maximization. In Proc. 15th AAMAS. 1395--1396. Google ScholarDigital Library
- Elchanan Mossel and Sebastien Roch. 2010. Submodularity of influence in social networks: From local to global. SIAM Journal on Computing 39 (2010), 2176--2188.Google ScholarDigital Library
- Seth A. Myers and Jure Leskovec. 2010. On the convexity of latent social network inference. In Proc. 22nd NIPS. 1741--1749. Google ScholarDigital Library
- Harikrishna Narasimhan, David C. Parkes, and Yaron Singer. 2015. Learnability of influence in networks. In Proc. 27th NIPS. 3168--3176. Google ScholarDigital Library
- George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming 14 (1978), 265--294. Google ScholarDigital Library
- Praneeth Netrapalli and Sujay Sanghavi. 2012. Learning the graph of epidemic cascades. In Proc. 12th ACM Sigmetrics. 211--222. Google ScholarDigital Library
- Kazumi Saito, Masahiro Kimura, Kouzou Ohara, and Hiroshi Motoda. 2009. Learning continuous-time information diffusion model for social behavioral data analysis. In Proc. 1st ACML: Advances in Machine Learning. 322--337. Google ScholarDigital Library
- Kazumi Saito, Masahiro Kimura, Kouzou Ohara, and Hiroshi Motoda. 2010. Generative models of information diffusion with asynchronous timedelay. In Proc. ACML. 193--208.Google Scholar
- Youze Tang, Yanchen Shi, and Xiaokui Xiao. 2015. Influence maximization in near-linear time: A martingale approach. In Proc. 35th ACM SIGMOD. 1539--1554. Google ScholarDigital Library
- Youze Tang, Xiaokui Xiao, and Yanchen Shi. 2014. Influence maximization: Near-optimal time complexity meets practical efficiency. In Proc. 34th ACM SIGMOD. 75--86. Google ScholarDigital Library
- Chi Wang, Wei Chen, and Yajun Wang. 2012. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery 25 (2012), 545--576.Google ScholarCross Ref
- Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie. 2010. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In Proc. 16th KDD. 1039--1048. Google ScholarDigital Library
- Amulya Yadav, Bryan Wilder, Eric Rice, Robin Petering, Jaih Craddock, Amanda Yoshioka-Maxwell, Mary Hemler, Laura Onasch-Vera, Milind Tambe, and Darlene Woo. 2017. Influence maximization in the field: The arduous journey from emerging to deployed application. In Proc. 16th AAMAS. 150--158. Google ScholarDigital Library
Index Terms
- Stability and Robustness in 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 ...
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 ...
On the Robustness of Influence Maximization Algorithms against Non-Adversarial Perturbations
ASONAM '17: Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2017Influence maximization is a combinatorial optimization problem on a graph: Given a social network, an influence maximization algorithm aims to find a set of influential (seed) nodes in the network such that the expected number of nodes influenced by the ...
Comments