Influence maximization algorithm: Review on current approaches and limitations
Article Sidebar
Main Article Content
Abstract
Influencing customers through social media is a new form of marketing. Recently, there were studies on the Influence Maximization (IM) problem, which aimed to identify influencers that can spread influence to a wider audience. The complex social media network requires efficient IM algorithms, in which small improvements will lead to a performance boost. In this research, recent articles on IM were reviewed. This review aims to identify the current approaches, enhancements, factors, diffusion models, and objectives of IM. In typical IM formulation, a social network is represented as a graph with nodes (user) and edges (relation). There are graph-based and non-graph-based IM approaches. Graph-based IM approaches include greedy and heuristic algorithms. The objectives of IM studies were optimizations on large or complex networks, on unknown networks, using bandit, using relation impacts, or general optimization. IM algorithms were continuously getting better. However, there are aspects that are still improvable, i.e. pre-calculation, thresholds estimation, seeds selection, integration of neural networks, and more importantly, real-life validation methods. This study will help in identifying possible improvements based on current IM limitations. Effective IM methods will help business users to identify influencers more accurately.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Statista. Most famous social network sites worldwide as of July 2018, ranked by number of active users (in millions) [Internet]. 2018. [cited 2018 Oct 3]. Available: https://www.statista.com/statistics/272014/global-social-networks-ranked-by-number-of-users/.
Tanase D, Garcia D, Garas A, Schweitzer F. Emotions and activity profiles of influential users in product reviews communities. Front Phys. 2015;3(87):1-12.
Odell P. The power of influencers: how brands can harness word-of-mouth and peer recommendations to connect with consumers. Norwalk: Chief Marketer; 2015.
Raudeliūnienė J, Davidavičienė V, Tvaronavičienė M, Jonuška L. Evaluation of advertising campaigns on social media networks. Sustainability. 2018;10(4):973.
Akar E, Yüksel HF, Z. Bulut A. The impact of social influence on the decision-making process of sports consumers on facebook. J Internet Appl Manag. 2015;6(2):5-27.
Pal SK, Kundu S, Murthy CA. Centrality measures, upper bound, and influence maximization in large scale directed social networks. Fundam Inform. 2014;130(3):317-42.
Arora A, Galhotra S, Ranu S. Debunking the myths of influence maximization. Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD’17); 2017 May 14-19; Chicago, USA. New York: ACM; 2017. p. 651-66.
Ko YY, Cho KJ, Kim SW. Efficient and effective influence maximization in social networks: a hybrid-approach. Inform Sci. 2018;465:144-61.
Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining; 2003 Aug 24-27; Washington, USA. New York: ACM; 2003. p. 137-46.
Ok J, Jin Y, Choi J , Shin J, Yi Y. Influence maximization over strategic diffusion in social networks. 48th Annual Conference on Information Sciences and Systems (CISS); 2014 Mar 19-21; Princeton, USA. USA: IEEE; 2014. p. 1-5.
Tang Y, Xiao X, Shi Y. Influence maximization: near-optimal time complexity meets practical efficiency. SIGMOD’14; 2014 Jun 22-27; Snowbird, USA. New York: ACM; 2014. p. 75-86.
Li M, Wang X, Gao K, Zhang S. A survey on information diffusion in online social networks: models and methods. Information. 2017;8(4):118.
Pastor-Satorras R, Castellano C, Mieghem PV, Vespignani A. Epidemic processes in complex networks. Rev Mod Phys. 2015;87(3):925.
Vega-Oliveros DA, Costa LdF, Rodrigues FA. Influence maximization by rumor spreading on correlated networks through community identification. Comm Nonlinear Sci Numer Simulat. 2020;83:105094.
Stoica AA, Chaintreau A. Fairness in social influence maximization. Proceedings of the 2019 World Wide Web Conference (WWW ’19 Companion); 2019 May 13-14; San Francisco, USA. New York: ACM; 2019. p. 569-74.
Erkol Ş, Castellano C, Radicchi F. Systematic comparison between methods for the detection of infuential spreaders in complex networks. Sci Rep. 2019;9(1):1-11.
Leskovec J, Krause A, Guestrin C, Faloutsos C, VanBriesen J, Glance N. Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2017 Aug 12-15; San Jose, USA. New York: ACM; 2007. p. 420-9.
Goyal A, Lu W, Lakshmanan LV. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. Proceedings of the 20th international conference companion on World Wide Web; 2011 Mar 28 – Apr 1; Hyderabad India. New York: ACM; 2011. p. 47-8.
Galhotra S, Arora A, Virinchi S, Roy S. ASIM: A scalable algorithm for influence maximization under the independent cascade model. Proceedings of the 24th International Conference on World Wide Web; 2015 May 18-22; Florence, Italy. New York: ACM; 2015. p. 35-6.
Morone F, Makse HA. Influence maximization in complex networks through optimal percolation. Nature. 2015;524:65-8.
Morone F, Min B, Bo L, Mari R, Makse H. Collective influence algorithm to find influencers via optimal percolation in massively large social media. Sci Rep. 2016;6:30062.
Tang Y, Shi Y, Xiao X. Influence maximization in near-linear time: a martingale approach. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data; 2015 May 31 - Jun 4; Melbourne, Australia. New York: ACM; 2015. pp. 1539-54.
Şimşek A, Kara R. Using swarm intelligence algorithms to detect influential individuals for influence maximization in social networks. Expert Syst Appl. 2018;114:224-36.
Panagopoulos G, Malliaros FD, Vazirgiannis M. DiffuGreedy: an influence maximization algorithm based on diffusion cascades. In: Aiello L, Cherifi C, Cherifi H, Lambiotte R, Lió P, Rocha L, editors. Complex Networks and Their Applications VII. Cham: Springer; 2018. p. 392-404.
Pham CV, Duong HV, Hoang HX, Thai MT. Competitive influence maximization within time and budget constraints in online social networks: an algorithmic approach. Appl Sci. 2019;9(11):2274.
Chung TY, Ali K, Wang CY. Deep reinforcement learning-based approach to tackle competitive influence maximization. Proceedings of 2019 ACM SIGKDD conference (KDD19 (MLG Workshop)) (MLG’19); 2019 Aug 5; Anchorage, USA. New York: ACM; 2019. p. 1-8.
Nguyen HT, Thai MT, Dinh TN. Stop-and-Stare: Optimal sampling algorithms for viral marketing in billion-scale networks. Proceedings of the 2016 International Conference on Management of Data; 2016 Jun 26 - Jul 1; San Francisco, USA. New York: ACM; 2016. p. 695-710.
Li H, Xu M, Bhowmick SS, Sun C, Jiang Z, Cui J. DISCO: influence maximization meets network embedding and deep learning. arXiv:1906.07378. 2019:1-14.
Nannicini G, Sartor G, Traversi E, Calvo RW. An exact algorithm for robust influence maximization. Math Program. 2020;183:419-53.
Kalimeris D, Kaplun G, Singer Y. Robust influence maximization for hyperparametric models. Proceedings of the 36th International Conference on Machine Learning; 2019 Jun 10-15; Long Beach, USA. PMLR; 2019. p. 3192-200.
Du N, Liang Y, Balcan MF, Gomez-Rodriguez M, Zha H, Song L. Scalable influence maximization for multiple products in continuous-time diffusion networks. J Mach Learn Res. 2017;18:1-45.
Chen X, Tan M, Zhao J, Yang T, Wu D, Zhao R. Identifying influential nodes in complex networks based on a spreading influence related centrality. Phys Stat Mech Appl. 2019;536:122481.
Lagrée P, Cappé O, Cautis B, Maniu S. Algorithms for online influencer marketing. arXiv:1702.05354. 2017:1-29.
Mothilal RK, Yadav A, Sharma A. Optimizing peer referrals for public awareness using contextual bandits. Proceedings of the Conference on Computing & Sustainable Societies; 2019 Jul 3-5; Accra, Ghana. New York: ACM; 2019. p. 74-85.
Wu X, Fu L, Meng J, Wang X. Evolving influence maximization. arXiv:1804.00802. 2018:1-23.
Vaswani S, Lakshmanan LV, Schmidt M. Influence maximization with bandits. arXiv:1503.00024. 2015:1-12.
Wen Z, Kveton B, Valko M, Vaswani S. Online influence maximization under independent cascade model with semi-bandit feedback. NIPS'17: Proceedings of the 31st International Conference on Neural Information Processing Systems; 2017 Dec 4-9; Long Beach, USA. New York: Curran Associates Inc; 2017. p. 1-11.
Wu Q, Li Z, Wang H, Chen W, Wang H. Factorization bandits for online influence maximization. KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining; 2019 Jul 4-8; Anchorage, USA. New York: ACM; 2019. p. 636-46.
Lei S, Maniu S, Mo L, Cheng R, Senellart P. Online influence maximization. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2015 Aug 10-13; Sydney, Australia. New York: ACM; 2015. p. 645-54.
Wang Y, Fan Q, Li Y, Tan KL. Real-Time influence maximization on dynamic social streams. PVLDB. 2017;10(7):805-16.
Yuan J, Tang S. No Time to observe: adaptive influence maximization with partial feedback. Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17); 2017 Aug 19-25; Melbourne, Australia. p. 3908-14.
Wang Y, Zhu J, Ming Q. Incremental influence maximization for dynamic social networks. In: Zou B, Han Q, Sun G, Jing W, Peng X, Lu, editors. Data Science. Singapore: Springer; 2017. p. 13-27.
Mohammadrezaei M, Shiri ME, Rahmani AM. Identifying fake accounts on social networks based on graph analysis and classification algorithms. Secur Comm Network. 2018;2018:5923156.
Martın EG, Lavesson N, Doroud M. Hashtags and followers : an experimental study of the online social network Twitter. J Market Manag. 2013;31(1):221-43.
Mihara S, Tsugawa S, Ohsaki H. Influence maximization problem for unknown social networks. 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM); 2015 Aug 25-28; Paris, France. USA: IEEE; 2015. p. 1539-46.
Wilder B, Immorlica N, Rice E, Tambe M. Maximizing influence in an unknown social network. The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18); 2018 Feb 2-7; New Orleans, USA. USA: AAAI Publications; 2018. p. 1-8.
Wilder B, Onasch-Vera L, Hudson J, Luna J, Wilson N, Petering R, et al. End-to-End influence maximization in the field. AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems; 2018 Jul 10-15; Stockholm, Sweden. Richland: IFAAMAS; 2018. p. 1414-22.
Yan B, Song K, Liu J, Meng F, Liu Y, Su H. On the maximization of influence over an unknown social network. AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems; 2019 May 13-17; Montreal, Canada. Richland: IFAAMAS; 2019. p. 2279-81.
Li Y, Chen W, Wang Y, Zhang ZL. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationship. Proceedings of the sixth ACM international conference on Web search and data mining; 2013 Feb 4-8; Rome, Italy. New York: ACM; 2013. p. 657-66.
Jendoubi S, Martin A. Evidential positive opinion influence measures for viral marketing. Knowl Inf Syst. 2020;62:1037-62.
Chen Y, Li H, Qu Q. Negative-Aware influence maximization on social networks. The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18); 2018 Feb 2-7; New Orleans, USA. USA: AAAI Publications; 2018. p. 1-2.
Guo J, Zhang P, Zhou C, Cao Y, Guo L. Personalized influence maximization on social networks. Proceedings of the 22nd ACM international conference on Information & Knowledge Management; 2013 Oct 27 – Nov 1; San Francisco, USA. New York: ACM; 2013. p. 199-208.
Razis G, Anagnostopoulos I. InfluenceTracker: Rating the impact of a twitter account. In: Iliadis L, Maglogiannis I, Papadopoulos H, Sioutas S, Makris C, editors. Artificial Intelligence Applications and Innovations. Berlin: Springer; 2014. p. 184-95.
Tang X, Yang CC. Ranking user influence in healthcare social media. ACM Trans Intell Syst Technol. 2012;3(4):73-96.
Aral S, Dhillon PS. Social influence maximization under empirical influence models. Nat Hum Behav. 2018;2:375-82.
Karampourniotis PD, Szymanski BK, Korniss G. Influence maximization for fixed heterogeneous thresholds. Sci Rep. 2019;9:5573.
Galhotra S, Arora A, Roy S. Holistic influence maximization: combining scalability and efficiency with opinion-aware models. Proceedings of the 2016 International Conference on Management of Data; 2016 Jun 26 - Jul 1; San Francisco, USA. New York: ACM; 2016. p. 743-58.
Cano AE, Mazumdar S, Ciravegna F. Social influence analysis in microblogging platforms – a topic-sensitive based approach. Semant Web. 2014;5(5):357-72.
Hamzehei A, Jiang S, Koutra D, Wong RK, Chen F. TSIM: Topic-based social influence measurement for social networks. Proceedings of the 14th Australasian Data Mining Conference; 2016 Dec 6-8; Canberra, Australia. New York: ACM; 2016. p. 1-9.
Aslay C, Barbieri N, Bonchi F, Baeza-Yates R. Online Topic-aware influence maximization queries. The 17th International Conference on Extending Database Technology (EDBT); 2014 Mar 24-28; Athens, Greece. p. 295-306.
Feng S, Chen X, Cong G, Zeng Y, Chee YM, Xiang Y. Influence maximization with novelty decay in social networks. Twenty-Eighth AAAI Conference on Artificial Intelligence; 2014 Jul 27-31; Québec, Canada. USA: AAAI; 2014. p. 37-43.
Wang F, Zhu Z, Liu P, Wang P. Influence maximization in social network considering memory effect and social reinforcement effect. Future internet. 2019;11(4):95.
Sankar CP, Asharaf S, Kumar KS. Learning from bees: an approach for influence maximization on viral campaigns. PLOS One. 2016;11(12):e0168125.
Talukder A, Alam MGR, Tran NH, Niyato D, Hong CS. Knapsack-based reverse influence maximization for target marketing in social networks. IEEE Access. 2019;7:44182-98.
Rossi M. Graph mining for influence maximization in social networks. France: Université Paris-Saclay; 2017.
Lv J, Guo J, Yang Z, Zhang W, Jocshi A. Improved algorithms of CELF and CELF++ for influence maximization. J Eng Sci Tech Rev. 2014;7(3):32-8.
Lv J, Guo J, Ren H. Efficient greedy algorithms for influence maximization in social networks. J Inform Process Syst. 2014;10(3):471-82.
Chen S, Fan J, Li G, Feng J, Tan Kl, Tang J. Online topic-aware influence maximization. PVLDB. 2015;8(6):666-77.
Derakhshan B. Influence maximization in large scale graphs. Helsinki: University of Helsinki; 2015.
Jia S, Chen L. Sampling based influence maximization on linear threshold model. J Phys: Conf Ser. 2018;989:012013.
Tang J, Zhang R, Yao Y, Zhao Z, Chai B, Li H. An adaptive discrete particle swarm optimization for influence maximization based on network community structure. Int J Mod Phys C. 2019;30(6):1950050.
Hua Y, Chen B, Yuan Y, Zhu G, Ma J. An influence maximization algorithm based on the mixed importance of nodes. Computers, Materials & Continua. 2019;59(2):517-31.
Arora N, Banati H. IM-GSO: A community directed group search optimization approach for influence maximization. Cybern Syst. 2018;49(7-8):497-520.
Panagopoulos G, Vazirgiannis M, Malliaros FD. Influence maximization via representation learning. arXiv:1904.08804. 2018:1-13.
Yang W, Brenner L, Giua A. Influence maximization in independent cascade networks based on activation probability computation. IEEE Access. 2019;7:13745-57.
He X, Kempe D. Robust influence maximization. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2016 Aug 13-17; San Francisco, USA. New York: ACM; 2016. p. 885-94.
Mohammadi A, Saraee M. Finding influential users for different time bounds in social networks using multi-objective optimization. Swarm Evol Comput. 2018;40:158-65.
Cheng S, Shen H, Huang J, Chen W, Cheng X. IMRank: influence maximization via finding self-consistent ranking. Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval; 2014 Jul 6-11; Gold Coast, Australia. New York: ACM; 2014. p. 475-84.
Gunnec D, Raghavan S, Zhang R. Tailored incentives and least cost influence maximization on social networks. USA: University of Maryland; 2017.
Jing D, Liu T. Context-based influence maximization with privacy protection in social networks. J Wireless Com Network. 2019;2019:142.
Shan X, Chen W, Li Q, Sun X, Zhang J. Cumulative activation in social networks. Sci China Inf Sci. 2019;62:52103.
Kuhnle A, Alim MA, Zhang H, Li X, Thai MT. Multiplex influence maximization in online social networks with heterogeneous diffusion models. IEEE Trans Comput Soc Syst. 2018;5(2):418-29.
Rao A, Spasojevic N, Li Z, DSouza T. Klout Score: measuring influence across multiple social network. BIG DATA '15: Proceedings of the 2015 IEEE International Conference on Big Data (Big Data); 2015 Oct 29 - Nov 1; Santa Clara, USA. USA: IEEE; 2015. p. 2282-9.
Li Y, Fan J, Ovchinnikov GV, Karras P. Maximizing multifaceted network influence. 35th IEEE International Conference on Data Engineering (ICDE 2019); 2019 Apr 8-11; Macau, China. USA: IEEE; 2019. p. 446-57.
Wang W, Street WN. Modeling and maximizing influence diffusion in social networks for viral marketing. Appl Netw Sci. 2018;3(6):1-26.
Aslay C, Lakshmanan LV, Lu W, X Xiao. Influence maximization in online social networks. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining; 2018 Feb 5-9; Los Angeles, USA. New York: ACM; 2018. p. 775-6.
Sun J, Tang J. Models and algorithms for social influence analysis. Proceedings of the sixth ACM international conference on Web search and data mining; 2013 Feb 4-8; Rome, Italy. New York: ACM; 2013. p. 775-6.
Christakis NA, Fowler JH. Connected: the surprising power of our social networks and how they shape our lives. New York: Little, Brown Spark; 2011.
Segev N, Avigdor N, Avigdor E. Measuring influence on instagram: a network-oblivious approach. arXiv: 1806.00881. 2018:1-5.
Erlandsson F, Bródka P, Borg A, Johnson H. Finding influential users in social media using association rule learning. Entropy. 2016;18(164):1-15.
Weskida M, Michalski R. Finding influentials in social networks using evolutionary algorithm. J Comput Sci. 2019;31:77-85.
Lynn CW, Lee DD. Statistical mechanics of influence maximization with thermal noise. Europhys Lett. 2017;117(6):66001.
Erkol S, Faqeeh A, Radicchi F. Influence maximization in noisy networks. Europhys Lett. 2018;123(5):58007.
Gonga M, Yan J, Shen B, Ma L, Cai Q. Influence maximization in social networks based on discrete particle swarm optimization. Inform Sci. 2016;367:600-14.