Youze Tang
ABSTRACT
Given a social network G and a constant $k$, the influence maximization problem asks for k nodes in G that (directly and indirectly) influence the largest number of nodes under a pre-defined diffusion model. This problem finds important applications in viral marketing, and has been extensively studied in the literature. Existing algorithms for influence maximization, however, either trade approximation guarantees for practical efficiency, or vice versa. In particular, among the algorithms that achieve constant factor approximations under the prominent independent cascade (IC) model or linear threshold (LT) model, none can handle a million-node graph without incurring prohibitive overheads.
This paper presents TIM, an algorithm that aims to bridge the theory and practice in influence maximization. On the theory side, we show that TIM runs in O((k+ l) (n+m) log n/ε2) expected time and returns a (1-1/e-ε)-approximate solution with at least 1 - n-l probability. The time complexity of TIM is near-optimal under the IC model, as it is only a log n factor larger than the Ω(m + n) lower-bound established in previous work (for fixed k, l, and ε). Moreover, TIM supports the triggering model, which is a general diffusion model that includes both IC and LT as special cases. On the practice side, TIM incorporates novel heuristics that significantly improve its empirical efficiency without compromising its asymptotic performance. We experimentally evaluate TIM with the largest datasets ever tested in the literature, and show that it outperforms the state-of-the-art solutions (with approximation guarantees) by up to four orders of magnitude in terms of running time. In particular, when k = 50, ε = 0.2, and l = 1, TIM requires less than one hour on a commodity machine to process a network with 41.6 million nodes and 1.4 billion edges. This demonstrates that influence maximization algorithms can be made practical while still offering strong theoretical guarantees.
- http://arxiv.org/abs/1404.0900.Google Scholar
- http://an.kaist.ac.kr/traces/WWW2010.html.Google Scholar
- S. Bharathi, D. Kempe, and M. Salek. Competitive influence maximization in social networks. In WINE, pages 306--311, 2007. Google ScholarDigital Library
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014. Google ScholarDigital Library
- W. Chen, W. Lu, and N. Zhang. Time-critical influence maximization in social networks with time-delayed diffusion process. In AAAI, 2012.Google ScholarDigital Library
- W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD, pages 1029--1038, 2010. Google ScholarDigital Library
- W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, pages 199--208, 2009. Google ScholarDigital Library
- W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, pages 88--97, 2010. Google ScholarDigital Library
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001. Google ScholarDigital Library
- A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. Learning influence probabilities in social networks. In WSDM, pages 241--250, 2010. Google ScholarDigital Library
- A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A data-based approach to social influence maximization. PVLDB, 5(1):73--84, 2011. Google ScholarDigital Library
- A. Goyal, W. Lu, and L. V. S. Lakshmanan. Celf++: optimizing the greedy algorithm for influence maximization in social networks. In WWW, pages 47--48, 2011. Google ScholarDigital Library
- A. Goyal, W. Lu, and L. V. S. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM, pages 211--220, 2011. Google ScholarDigital Library
- M. Granovetter. Threshold models of collective behavior. American Journal of Sociology, 83(6):1420--1443, 1978.Google ScholarCross Ref
- E. M. J. Goldenberg, B. Libai. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211--223, 2001.Google ScholarCross Ref
- E. M. J. Goldenberg, B. Libai. Using complex systems analysis to advance marketing theory development. American Journal of Sociology, 9:1, 2001.Google Scholar
- K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In ICDM, pages 918--923, 2012. Google ScholarDigital Library
- D. Kempe, J. M. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- D. Kempe, J. M. Kleinberg, and É. Tardos. In fluential nodes in a diffusion model for social networks. In ICALP, pages 1127--1138, 2005. Google ScholarDigital Library
- J. Kim, S.-K. Kim, and H. Yu. Scalable and parallelizable processing of influence maximization for large-scale social networks. InICDE, pages 266--277, 2013. Google ScholarDigital Library
- K. Kutzkov, A. Bifet, F. Bonchi, and A. Gionis. Strip: stream learning of influence probabilities. In KDD, pages 275--283, 2013. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007. Google ScholarDigital Library
- Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang. In fluence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In WSDM, pages 657--666, 2013. Google ScholarDigital Library
- W. Lu, F. Bonchi, A. Goyal, and L. V. S. Lakshmanan. The bang for the buck: fair competitive viral marketing from the host perspective. In KDD, pages 928--936, 2013. Google ScholarDigital Library
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google ScholarDigital Library
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002. Google ScholarDigital Library
- K. Saito, N. Mutoh, T. Ikeda, T. Goda, and K. Mochizuki. Improving search efficiency of incremental variable selection by using second-order optimal criterion. In KES (3), pages 41--49, 2008. Google ScholarDigital Library
- T. Schelling. Micromotives and Macrobehavior. W.W.Norton & Company, 2006.Google Scholar
- L. Seeman and Y. Singer. Adaptive seeding in social networks. In FOCS, pages 459--468, 2013. Google ScholarDigital Library
- V. V. Vazirani. Approximation Algorithms. Springer, 2002. Google ScholarDigital Library
- C. Wang, W. Chen, and Y. Wang. Scalable in fluence maximization for independent cascade model in large-scale social networks. Data Min. Knowl. Discov., 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 in fluential nodes in mobile social networks. In KDD, pages 1039--1048, 2010. Google ScholarDigital Library
Index Terms
- Influence maximization: near-optimal time complexity meets practical efficiency
Recommendations
Online Processing Algorithms for Influence Maximization
SIGMOD '18: Proceedings of the 2018 International Conference on Management of DataInfluence maximization is a classic and extensively studied problem with important applications in viral marketing. Existing algorithms for influence maximization, however, mostly focus on offline processing, in the sense that they do not provide any ...
Continuous Influence Maximization
Imagine we are introducing a new product through a social network, where we know for each user in the network the function of purchase probability with respect to discount. Then, what discounts should we offer to those social network users so that, ...
Influence Estimation and Maximization in Continuous-Time Diffusion Networks
If a piece of information is released from a set of media sites, can it spread, in 1 month, to a million web pages? Can we efficiently find a small set of media sites among millions that can maximize the spread of the information, in 1 month? The two ...
Comments