A Dynamic Metaheuristic Algorithm for Influence Maximization in Social Networks

Document Type : Original Article

Authors

1 Ph.D. student, Computer Department, Miyaneh Branch, Islamic Azad University, Miyaneh, Iran

2 Professor, Computer Department, Miyaneh Branch, Islamic Azad University, Miyaneh, Iran

3 Assistant Professor, Computer Department, Miyaneh Branch, Islamic Azad University, Miyaneh, Iran

Abstract

During the very last decade, people have been spending lots of time working with social networks to interact with friends and to share information, thoughts, news, and etc. These social networks comprise a very important part of our daily lives. Along with the exploitation of the development of social networks, finding influential individuals in a social network has many practical functions in marketing, politics, and even control of the diseases. In the present research, a novel method called the dynamic generalized vulture algorithm has been proposed to solve influence maximization problems. Regarding the fact that in real world social networks own very dynamic and scalable nature, through our proposed algorithm, we have considered two important criteria which have been rarely taken into consideration in previous projects. The first criterion is due to the network structure change during time pass and the other refers to scalability. The suggested algorithm was measured considering standard data sets. The results showed that the proposed algorithm has been more scalable and has had higher precision in locating the most influential tops in such networks compared with other algorithms due to the reduction of search area and using several different mechanisms during navigation and optimization, balance creation and moving through these stages.

Keywords

Smiley face

References

[1]          N. Hafiene, W. Karoui, and L. B. Romdhane, "Influential nodes detection in dynamic social networks: A survey," Expert Systems with Applications, vol. 159, p. 113642, 2020.
[2]    J. J. Lotf, M. A. Azgomi, and M. R. E. Dishabi, "An improved influence maximization method for social networks based on genetic algorithm," Physica A: Statistical Mechanics and its Applications, vol. 586, p. 126480, 2022.
[3]          D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, pp. 137-146: ACM.
[4]          Z. Aghaee and S. Kianian, "Efficient influence spread estimation for influence maximization," Social Network Analysis and Mining, vol. 10, no. 1, pp. 1-21, 2020.
[5]    H. A. Beni, Z. Aghaee, A. Bouyer, and M. Vahidipour, "IMT: selection of top-k nodes based on the topology structure in social networks," in 2020 6th International Conference on Web Research (ICWR), 2020, pp. 84-88: IEEE.
[6]          Z. Aghaee, H. A. Beni, S. Kianian, and M. Vahidipour, "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), 2020, pp. 119-125: IEEE.
[7]          S. Peng, Y. Zhou, L. Cao, S. Yu, J. Niu, and W. Jia, "Influence analysis in social networks: A survey," Journal of Network and Computer Applications, vol. 106, pp. 17-32, 2018.
[8]          B. Chang, T. Xu, Q. Liu, and E.-H. Chen, "Study on information diffusion analysis in social networks and its applications," International Journal of Automation and Computing, vol. 15, no. 4, pp. 377-401, 2018.
[9]          S. Banerjee, M. Jenamani, and D. K. Pratihar, "A survey on influence maximization in a social network," Knowledge and Information Systems, vol. 62, no. 9, pp. 3417-3455, 2020.
[10]         S. S. Singh, A. Kumar, K. Singh, and B. Biswas, "IM‐SSO: Maximizing influence in social networks using social spider optimization," Concurrency and Computation: Practice and Experience, vol. 32, no. 2, p. e5421, 2020.
[11]                        J. Shang, S. Zhou, X. Li, L. Liu, and H. Wu, "CoFIM: A community-based framework for influence maximization on large-scale networks," Knowledge-Based Systems, vol. 117, pp. 88-100, 2017.
[12]         M. Heidari, M. Asadpour, and H. Faili, "SMG: Fast scalable greedy algorithm for influence maximization in social networks," Physica A: Statistical Mechanics and its Applications, vol. 420, pp. 124-133, 2015.
[13]                        J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, "Cost-effective outbreak detection in networks," in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, pp. 420-429: ACM.
[14]         A. Goyal, W. Lu, and L. V. S. Lakshmanan, "CELF++: optimizing the greedy algorithm for influence maximization in social networks," presented at the Proceedings of the 20th international conference companion on World wide web, Hyderabad, India, 2011. 
[15]         Y. Tang, X. Xiao, and Y. Shi, "Influence maximization: Near-optimal time complexity meets practical efficiency," in Proceedings of the 2014 ACM SIGMOD international conference on Management of data, 2014, pp. 75-86.
[16]         H. T. Nguyen, M. T. Thai, and T. N. Dinh, "A billion-scale approximation algorithm for maximizing benefit in viral marketing," IEEE/ACM Transactions On Networking, vol. 25, no. 4, pp. 2419-2429, 2017.
[17]                        C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, "Maximizing social influence in nearly optimal time," in Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, 2014, pp. 946-957: SIAM.
[18]         W. Chen, Y. Wang, and S. Yang, "Efficient influence maximization in social networks," presented at the Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, Paris, France, 2009. 
[19]         S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng, "Staticgreedy: solving the scalability-accuracy dilemma in influence maximization," in Proceedings of the 22nd ACM international conference on Information & Knowledge Management, 2013, pp. 509-518.
[20]         J. Lv, J. Guo, and H. Ren, "Efficient Greedy Algorithms for Influence Maximization in Social Networks," JIPS, vol. 10, no. 3, pp. 471-482, 2014.
[21]         N. Samadi and A. Bouyer, "Identifying influential spreaders based on edge ratio and neighborhood diversity measures in complex networks," Computing, vol. 101, no. 8, pp. 1147-1175, 2019.
[22]                        J.-X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao, "Identifying a set of influential spreaders in complex networks," Scientific reports, vol. 6, no. 1, pp. 1-10, 2016.
[23]         K. Berahmand, A. Bouyer, and N. Samadi, "A new local and multidimensional ranking measure to detect spreaders in social networks," Computing, vol. 101, no. 11, pp. 1711-1733, 2019.
[24]         D. Liu, Y. Jing, J. Zhao, W. Wang, and G. Song, "A fast and efficient algorithm for mining top-k nodes in complex networks," Scientific reports, vol. 7, no. 1, pp. 1-8, 2017.
[25]         Z.-L. Luo, W.-D. Cai, Y.-J. Li, and D. Peng, "A pagerank-based heuristic algorithm for influence maximization in the social network," in Recent progress in data engineering and internet technology: Springer, 2012, pp. 485-490.
[26]                        S. Ahajjam and H. Badir, "Identification of influential spreaders in complex networks using HybridRank algorithm," Scientific reports, vol. 8, no. 1, pp. 1-10, 2018.
[27]         L. Qiu, X. Tian, S. Sai, and C. Gu, "LGIM: A global selection algorithm based on local influence for influence maximization in social networks," IEEE Access, vol. 8, pp. 4318-4328, 2019.
[28]         W. Li et al., "Three-hop velocity attenuation propagation model for influence maximization in social networks," World Wide Web, vol. 23, no. 2, pp. 1261-1273, 2020.
[29]         Z. Aghaee and S. Kianian, "Influence maximization algorithm based on reducing search space in the social networks," SN Applied Sciences, vol. 2, no. 12, pp. 1-14, 2020.
[30]         Y. Zhao, S. Li, and F. Jin, "Identification of influential nodes in social networks with community structure based on label propagation," Neurocomputing, vol. 210, no. C, pp. 34-44, 2016.
[31]         F. Ullah and S. Lee, "Identification of influential nodes based on temporal-aware modeling of multi-hop neighbor interactions for influence spread maximization," Physica A: Statistical Mechanics and its Applications, vol. 486, pp. 968-985, 2017.
[32]         D. Cai, Z. Wang, N. Wang, and D. Wei, "A new method for identifying influential nodes based on DS evidence theory," in 2017 29th Chinese Control And Decision Conference (CCDC), 2017, pp. 4603-4609: IEEE.
[33]         E. B. A. Karimi, M. Nemati, M. Saleh Esfehani, "Identifying Influential Nodes in Social Networks by Integrating the Centrality Method and Node Activity," Journal of  Electronical & Cyber Defence, vol. 8, no. 3, pp. 1-11, 2020.(In Persian)
[34]         Q. Jiang, G. Song, C. Gao, Y. Wang, W. Si, and K. Xie, "Simulated annealing based influence maximization in social networks," in Twenty-fifth AAAI conference on artificial intelligence, 2011.
[35]         C.-W. Tsai, Y.-C. Yang, and M.-C. Chiang, "A genetic newgreedy algorithm for influence maximization in social network," in 2015 IEEE International Conference on Systems, Man, and Cybernetics, 2015, pp. 2549-2554: IEEE.
[36]         M. Gong, J. Yan, B. Shen, L. Ma, and Q. Cai, "Influence maximization in social networks based on discrete particle swarm optimization," Information Sciences, vol. 367, pp. 600-614, 2016.
[37]                        L. Cui et al., "DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks," Journal of Network and Computer Applications, vol. 103, pp. 119-130, 2018.
[38]         J. Tang et al., "Maximizing the spread of influence via the collective intelligence of discrete bat algorithm," Knowledge-Based Systems, vol. 160, pp. 88-103, 2018.
[39]         B. Abdollahzadeh, F. S. Gharehchopogh, and S. Mirjalili, "African vultures optimization algorithm: A new nature-inspired metaheuristic algorithm for global optimization problems," Computers & Industrial Engineering, vol. 158, p. 107408, 2021.
[40]         J. Tang, R. Zhang, P. Wang, Z. Zhao, L. Fan, and X. Liu, "A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks," Knowledge-Based Systems, vol. 187, p. 104833, 2020.
[41]         B. Abdollahzadeh, F. Soleimanian Gharehchopogh, and S. Mirjalili, "Artificial gorilla troops optimizer: a new nature‐inspired metaheuristic algorithm for global optimization problems," International Journal of Intelligent Systems, vol. 36, no. 10, pp. 5887-5958, 2021.
[42]         S. A. Myers and J. Leskovec, "The bursty dynamics of the twitter information network," in Proceedings of the 23rd international conference on World wide web, 2014, pp. 913-924.
[43]         D. Kempe, J. Kleinberg, and É. Tardos, "Maximizing the spread of influence through a social network," Theory of Computing, vol. Volume 11, p. 42, 2015.
[44]                        H. Shayanfar and F. S. Gharehchopogh, "Farmland fertility: A new metaheuristic algorithm for solving continuous optimization problems," Applied Soft Computing, vol. 71, pp. 728-746, 2018.
[45]         E. Cohen, D. Delling, T. Pajor, and R. F. Werneck, "Computing classic closeness centrality, at scale," presented at the Proceedings of the second ACM conference on Online social networks, Dublin, Ireland, 2014.Available: https://doi.org/10.1145/2660460.2660465
[46]         M. Riondato and E. M. Kornaropoulos, "Fast approximation of betweenness centrality through sampling," Data Mining and Knowledge Discovery, vol. 30, no. 2, pp. 438-475, 2016.
[47]         H. Kingi et al., "A numerical evaluation of the accuracy of influence maximization algorithms," Social Network Analysis and Mining, vol. 10, no. 1, p. 70, 2020/08/24 2020.
[48]         J. K. David Kempe, and Éva Tardos, "Maximizing the Spread of Influence through a Social Network," Theory of Computing, vol. Volume 11 pp. 105-147, April 22, 2015.
Electronic and Cyber Defense
Volume 11, Issue 2 - Serial Number 42
No. 42, Summer
July 2023
Pages 57-69

Files

History

  • Receive Date: 02 August 2022
  • Revise Date: 28 January 2023
  • Accept Date: 30 January 2023
  • Publish Date: 22 June 2023

Share

How to cite

Statistics