Top

Computing

Published in:

15-09-2021 | Survey Article

A survey on meta-heuristic algorithms for the influence maximization problem in the social networks

Authors: Zahra Aghaee, Mohammad Mahdi Ghasemi, Hamid Ahmadi Beni, Asgarali Bouyer, Afsaneh Fatemi

Published in: Computing | Issue 11/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The different communications of users in social networks play a key role in effect to each other. The effect is important when they can achieve their goals through different communications. Studying the effect of specific users on other users has been modeled on the influence maximization problem on social networks. To solve this problem, different algorithms have been proposed that each of which has attempted to improve the influence spread and running time than other algorithms. Due to the lack of a review of the meta-heuristic algorithms for the influence maximization problem so far, in this paper, we first perform a comprehensive categorize of the presented algorithms for this problem. Then according to the efficient results and significant progress of the meta-heuristic algorithms over the last few years, we describe the comparison, advantages, and disadvantages of these algorithms.

next article Towards big services: a synergy between service computing and parallel programming

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining

Aghaee Z, Kianian S (2020) Efficient influence spread estimation for influence maximization. Soc Netw Anal Min 10(1):1–21CrossRef

Beni HA et al (2020) IMT: selection of top-k nodes based on the topology structure in social networks. In: 2020 6th international conference on web research (ICWR). IEEE

Aghaee Z et al (2020) A heuristic algorithm focusing on the rich-club phenomenon for the influence maximization problem in social networks. In: 2020 6th International Conference on Web Research (ICWR). IEEE

Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining

Li W et al (2020) Three-hop velocity attenuation propagation model for influence maximization in social networks. World Wide Web 23(2):1261–1273CrossRef

Sumith N, Annappa B, Bhattacharya S (2018) Influence maximization in large social networks: Heuristics, models and parameters. Futur Gener Comput Syst 89:777–790CrossRef

Sanatkar MR (2020) The dynamics of polarized beliefs in networks governed by viral diffusion and media influence. Soc Netw Anal Min 10(1):1–21CrossRef

Saxena B, Kumar P (2019) A node activity and connectivity-based model for influence maximization in social networks. Soc Netw Anal Min 9(1):40CrossRef

10.

Peng S et al (2018) Influence analysis in social networks: A survey. J Netw Comput Appl 106:17–32CrossRef

11.

Tang J, Tang X, Yuan J (2018) An efficient and effective hop-based approach for influence maximization in social networks. Soc Netw Anal Min 8(1):10CrossRef

12.

Chang B et al (2018) Study on information diffusion analysis in social networks and its applications. Int J Autom Comput 15(4):377–401CrossRef

13.

Banerjee S, Jenamani M, Pratihar DK (2018) A survey on influence maximization in a social network. arXiv preprint arXiv:1808.05502

14.

Sun J, Tang J (2011) A survey of models and algorithms for social influence analysis. Social network data analytics. Springer, pp 177–214CrossRef

15.

Li M et al (2017) A survey on information diffusion in online social networks: Models and methods. Information 8(4):118CrossRef

16.

Pei S, Makse HA (2013) Spreading dynamics in complex networks. J Stat Mech: Theory Exp 2013(12):P12002CrossRef

17.

Pastor-Satorras R et al (2015) Epidemic processes in complex networks. Rev Mod Phys 87(3):925MathSciNetCrossRef

18.

Samadi N, Bouyer A (2019) Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks. Computing 101(8):1147–1175MathSciNetCrossRef

19.

Zafarani R et al (2014) Information diffusion in social media. Social Media mining: an introduction. NP, Cambridge UP

20.

Rui X et al (2019) A reversed node ranking approach for influence maximization in social networks. Appl Intell 49(7):2684–2698CrossRef

21.

Singh SS et al (2020) IM-SSO: Maximizing influence in social networks using social spider optimization. Concurr Comput Pract Exp 32(2):e5421

22.

Shang J et al (2017) CoFIM: a community-based framework for influence maximization on large-scale networks. Knowl-Based Syst 117:88–100CrossRef

23.

Leskovec J et al (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining

24.

Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

25.

Goyal A, Lu W, Lakshmanan LV (2011) Celf++ optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on World wide web

26.

Cheng S et al (2013) Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In: Proceedings of the 22nd ACM international conference on Information and knowledge management

27.

Heidari M, Asadpour M, Faili H (2015) SMG: Fast scalable greedy algorithm for influence maximization in social networks. Phys A 420:124–133CrossRef

28.

Zhang J-X et al (2016) Identifying a set of influential spreaders in complex networks. Sci Rep 6:27823CrossRef

29.

Berahmand K, Bouyer A, Samadi N (2019) A new local and multidimensional ranking measure to detect spreaders in social networks. Computing 101(11):1711–1733MathSciNetCrossRef

30.

Liu D et al (2017) A fast and efficient algorithm for mining top-k nodes in complex networks. Sci Rep 7:43330CrossRef

31.

Luo Z-L et al (2012) A pagerank-based heuristic algorithm for influence maximization in the social network. Recent progress in data engineering and internet technology. Springer, pp 485–490CrossRef

32.

Ahajjam S, Badir H (2018) Identification of influential spreaders in complex networks using HybridRank algorithm. Sci Rep 8(1):1–10CrossRef

33.

Qiu L et al (2019) LGIM: A global selection algorithm based on local influence for influence maximization in social networks. IEEE Access

34.

Tang Y, Xiao X, Shi Y (2014) Influence maximization: Near-optimal time complexity meets practical efficiency. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data

35.

Tang Y, Shi Y, Xiao X (2015) Influence maximization in near-linear time: A martingale approach. In: Proceedings of the 2015 ACM SIGMOD international conference on management of data

36.

Aghaee Z, Kianian S (2020) Influence maximization algorithm based on reducing search space in the social networks. SN Appl Sci 2(12):1–14CrossRef

37.

Wang Y et al (2010) Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining

38.

Zhao Y, Li S, Jin F (2016) Identification of influential nodes in social networks with community structure based on label propagation. Neurocomputing 210:34–44CrossRef

39.

Qiu L et al (2019) PHG: a three-phase algorithm for influence maximization based on community structure. IEEE Access 7:62511–62522CrossRef

40.

Singh SS et al (2019) C2IM: community based context-aware influence maximization in social networks. Phys A 514:796–818MathSciNetCrossRef

41.

Bouyer A, Ahmadi H (2018) A new greedy method based on cascade model for the influence maximization problem in social networks. J Inf Commun Technol 10(37):85–100

42.

Banerjee S, Jenamani M, Pratihar DK (2019) ComBIM: a community-based solution approach for the Budgeted Influence Maximization Problem. Expert Syst Appl 125:1–13CrossRef

43.

Beni HA, Bouyer A (2020) TI‑SC: top‑k influential nodes selection based on community detection and scoring criteria in social networks

44.

Kimura M, Saito K (2006) Tractable models for information diffusion in social networks. In: European conference on principles of data mining and knowledge discovery. Springer, Berlin

45.

Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE international conference on data mining. IEEE

46.

Chen W, Wang C, Wang Y (2010) Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining

47.

Goyal A, Lu W, Lakshmanan LV (2011) Simpath: An efficient algorithm for influence maximization under the linear threshold model. In: 2011 IEEE 11th international conference on data mining. IEEE

48.

Wang C, Chen W, Wang Y (2012) Scalable influence maximization for independent cascade model in large-scale social networks. Data Min Knowl Disc 25(3):545–576MathSciNetCrossRef

49.

Kim J, Kim S-K, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks? In: 2013 IEEE 29th international conference on data engineering (ICDE). IEEE

50.

Jiang Q et al (2011) Simulated annealing based influence maximization in social networks. In: Twenty-fifth AAAI conference on artificial intelligence

51.

Tsai C-W, Yang Y-C, Chiang M-C (2015) A genetic newgreedy algorithm for influence maximization in social network. In: 2015 IEEE international conference on systems, man, and cybernetics. IEEE

52.

Gong M et al (2016) Influence maximization in social networks based on discrete particle swarm optimization. Inf Sci 367:600–614CrossRef

53.

Cui L et al (2018) DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. J Netw Comput Appl 103:119–130CrossRef

54.

Tang J et al (2018) Maximizing the spread of influence via the collective intelligence of discrete bat algorithm. Knowl-Based Syst 160:88–103CrossRef

55.

Tang J et al (2019) Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization. Phys A 513:477–496CrossRef

56.

Tang J et al (2019) An adaptive discrete particle swarm optimization for influence maximization based on network community structure. Int J Modern Phys C (IJMPC) 30(06):1–21MathSciNet

57.

Ma L, Liu Y (2019) Maximizing three-hop influence spread in social networks using discrete comprehensive learning artificial bee colony optimizer. Appl Soft Comput 83:105606CrossRef

58.

Zareie A, Sheikhahmadi A, Jalili M (2020) Identification of influential users in social network using gray wolf optimization algorithm. Expert Syst Appl 142:112971CrossRef

59.

Tang J et al (2020) A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks. Knowl-Based Syst 187:104833CrossRef

60.

Krömer P, Nowaková J (2017) Guided genetic algorithm for the influence maximization problem. In: international computing and combinatorics conference. Springer, Berlin

61.

Weskida M, Michalski R (2016) Evolutionary algorithm for seed selection in social influence process. In: 2016 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM). IEEE

62.

da Silva AR et al (2018) Influence maximization in network by genetic algorithm on linear threshold model. In: international conference on computational science and its applications. Springer, Berlin

63.

Bucur D, Iacca G (2016) Influence maximization in social networks with genetic algorithms. In: European conference on the applications of evolutionary computation. Springer, Berlin

64.

Bouyer A, Roghani H (2020) LSMD: a fast and robust local community detection starting from low degree nodes in social networks. Futur Gener Comput Syst 113:41–57CrossRef

65.

Taheri S, Bouyer A (2020) Community detection in social networks using affinity propagation with adaptive similarity matrix. Big Data 8(3):189–202CrossRef

Title: A survey on meta-heuristic algorithms for the influence maximization problem in the social networks
Authors: Zahra Aghaee
Mohammad Mahdi Ghasemi
Hamid Ahmadi Beni
Asgarali Bouyer
Afsaneh Fatemi
Publication date: 15-09-2021
Publisher: Springer Vienna
Published in: Computing / Issue 11/2021
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-021-00945-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 11/2021

Towards big services: a synergy between service computing and parallel programming

Detector-based component model abstraction for microservice-based systems

Blockchain-based public ecosystem for auditing security of software applications

A prediction-based model for virtual machine live migration monitoring in a cloud datacenter

A service classification model for IoT services discovery

A data fusion based data aggregation and sensing technique for fault detection in wireless sensor networks

Premium Partner