Abstract
Given a social network G, the influence maximization (IM) problem seeks a set S of k seed nodes in G to maximize the expected number of nodes activated via an influence cascade starting from S. Although a lot of algorithms have been proposed for IM, most of them only work under the non-adaptive setting, i.e., when all k seed nodes are selected before we observe how they influence other users. In this paper, we study the adaptive IM problem, where we select the k seed nodes in batches of equal size b, such that the choice of the i-th batch can be made after the influence results of the first i - 1 batches are observed. We propose the first practical algorithms for adaptive IM with an approximation guarantee of 1 − exp(ξ − 1) for b = 1 and 1 − exp(ξ − 1 + 1/e) for b > 1, where ξ is any number in (0, 1). Our approach is based on a novel AdaptGreedy framework instantiated by non-adaptive IM algorithms, and its performance can be substantially improved if the non-adaptive IM algorithm has a small expected approximation error. However, no current non-adaptive IM algorithms provide such a desired property. Therefore, we further propose a non-adaptive IM algorithm called EPIC, which not only has the same worst-case performance bounds with that of the state-of-the-art non-adaptive IM algorithms, but also has a reduced expected approximation error. We also provide a theoretical analysis to quantify the performance gain brought by instantiating AdaptGreedy using EPIC, compared with a naive approach using the existing IM algorithms. Finally, we use real social networks to evaluate the performance of our approach through extensive experiments, and the experimental experiments strongly corroborate the superiorities of our approach.
- https://bit.ly/2I3A99p.Google Scholar
- http://snap.stanford.edu.Google Scholar
- https://sourceforge.net/projects/im-imm/.Google Scholar
- A. Badanidiyuru, C. Papadimitriou, A. Rubinstein, L. Seeman, and Y. Singer. Locally adaptive optimization: adaptive seeding for monotone submodular functions. In SODA, 2016. Google ScholarDigital Library
- N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. In ICDM, pages 81--90, 2012. Google ScholarDigital Library
- D. Berend and A. Kontorovich. A sharp estimate of the binomial mean absolute deviation with applications. Statistics & Probability Letters, 83(4):1254--1259, 2013.Google ScholarCross Ref
- C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014. 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
- Y. Chen and A. Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In Proc. of ICML, pages 160--168, 2013. Google ScholarDigital Library
- D. P. Dubhashi and A. Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google ScholarDigital Library
- D. Golovin and A. Krause. Adaptive submodularity: theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42(1):427--486, 2011. Google ScholarDigital Library
- K. Han, Y. He, X. Xiao, S. Tang, F. Gui, C. Xu, and J. Luo. Budget-constrained organization of influential social events. In ICDE, pages 917--928, 2018.Google ScholarCross Ref
- K. Han, C. Xu, F. Gui, S. Tang, H. Huang, and J. Luo. Discount allocation for revenue maximization in online social networks. In MobiHoc, 2018.Google ScholarDigital Library
- T. Horel and Y. Singer. Scalable methods for adaptively seeding a social network. In WWW, pages 623--624, 2015. Google ScholarDigital Library
- K. Huang, S. Wang, G. S. Bevilacqua, X. Xiao, and L. V. S. Lakshmanan. Revisiting the stop-and-stare algorithms for influence maximization. PVLDB, 10(9):913--924, 2017. 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
- H. T. Nguyen, M. T. Thai, and T. N. Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In SIGMOD, pages 695--710, 2016. Google ScholarDigital Library
- H. T. Nguyen, M. T. Thai, and T. N. Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. CoRR, abs/1605.07990v3, Feb 22, 2017.Google Scholar
- L. Seeman and Y. Singer. Adaptive seeding in social networks. In FOCS, pages 459--468, 2013. Google ScholarDigital Library
- J. Tang, X. Tang, X. Xiao, and J. Yuan. Online processing algorithms for influence maximization. In SIGMOD, 2018. Google ScholarDigital Library
- J. Tang, X. Tang, and J. Yuan. Influence maximization meets efficiency and effectiveness: A hop-based approach. In ASONAM, pages 64--71, 2017. Google ScholarDigital Library
- J. Tang, X. Tang, and J. Yuan. An efficient and effective hop-based approach for inluence maximization in social networks. Social Network Analysis and Mining, 8(10), 2018.Google Scholar
- Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In SIGMOD, pages 1539--1554, 2015. Google ScholarDigital Library
- Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD, pages 75--86, 2014. Google ScholarDigital Library
- S. Vaswani and L. V. S. Lakshmanan. Adaptive influence maximization in social networks: Why commit when you can adapt? arXiv: 1604.08171, 2016.Google Scholar
- A. Yadav, H. Chan, A. Xin Jiang, H. Xu, E. Rice, and M. Tambe. Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty. In AAMAS, pages 740--748, 2016. Google ScholarDigital Library
Index Terms
- Efficient algorithms for adaptive influence maximization
Recommendations
Efficient approximation algorithms for adaptive influence maximization
AbstractGiven a social network G and an integer k, the influence maximization (IM) problem asks for a seed set S of k nodes from G to maximize the expected number of nodes influenced via a propagation model. The majority of the existing algorithms for the ...
Adaptive influence maximization under fixed observation time-step
AbstractThe influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the ...
Highlights- We study the adaptive influence maximization problem under a general model.
- We ...
Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization
We consider the adaptive influence maximization problem: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the full-adoption feedback model, after selecting each seed, the seed-picker ...
Comments