Influence Maximization in Social Networks Using Discrete Manta-Ray Foraging Optimization Algorithm and Combination of Centrality Criteria

Document Type : Original Article

Authors

Department of Computer Engineering, Shab.C., Islamic Azad University, Shabestar, Iran

Abstract

Influence Maximization (IM) is a fundamental problem in social network analysis that seeks to identify a small set of highly influential nodes that can maximize the spread of information. Due to its NP-hard nature, finding an exact solution is computationally infeasible for large-scale networks. To address this, this paper introduces an enhanced discrete Manta-Ray Foraging Optimization (MRFO) algorithm tailored for IM. The proposed method integrates degree, closeness, and betweenness centrality measures into the fitness function and introduces a fused centrality index to improve the identification of influential nodes. To handle the discrete search space, the continuous MRFO is adapted with novel discretization mechanisms. Experimental evaluations on five real-world networks (NetScience, Email, Hamsterster, Ego-Facebook, and Pages-PublicFigure) demonstrate that the proposed method achieves higher influence spread compared to existing baseline algorithms, with average improvements of 14.63%, 12.81%, 19.03%, 15.24%, and 18.76%, respectively. These results validate the effectiveness, robustness, and practical applicability of the proposed approach for large-scale IM.

Keywords

Main Subjects

References

  1. Aghaee, M. M. Ghasemi, H. A. Beni, A. Bouyer, and A. Fatemi. (2021, Mar.). A Survey on Meta-Heuristic Algorithms for the IM Problem in Social Networks. Computing. [Online]. pp. 2437–2477. Available: https://doi.org/10.1007/s00607-021-00945-7
  2. Ye, Y. Chen, and W. Han. (2022, Oct.). IM in social networks: theories, methods and challenges. Array. [online]. 16, p. 100264. Available: https://doi.org/10.1016/j.array.2022.100264
  3. Aghaee and S. Kianian. (2020, Apr.). IM algorithm based on reducing search space in the social networks. SN Applied Sciences .[online]. 2, pp. 1-14. Available: https://doi.org/10.1007/s42452-020-03812-w
  4. Dey, A. Chatterjee, and S. Roy. (2019, Jul.). IM in online social network using different centrality measures as seed node of information propagation. Sādhanā Department of Computer Science and Engineering. [online]. 44(9), pp. 1-13. Available: https://doi.org/10.1007/s12046-019-1189-7.
  5. Wang, L. Ma, C. Wang, N.-g. Xie, J. M. Koh, and K. H. Cheong. (2021, May.). Identifying influential spreaders in social networks through discrete moth-flame optimization. IEEE Transactions on Evolutionary Computation. [online]. 25(6), pp. 1091-1102. Available: http://dx.doi.org/10.1109/TEVC.2021.3081478
  6. C. Freeman. (1978, Sep.). Centrality in social networks: Conceptual clarification. Social Networks. [Online]. 1(3), pp. 215–239. Available: https://dx.doi.org/10.1016/0378-8733(78)90021-7
  7. Kempe, J. Kleinberg, and É. Tardos. (2003, Aug.). Maximizing the spread of influence through a social network. Presented at Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. [Online]. Available: https://doi.org/10.1145/956750.956769
  8. Brin and L. Page. (1998, Apr.). The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems. [Online]. 30(1–7), pp. 107–117. Available: https://dx.doi.org/10.1016/S0169-7552(98)00110-X
  9. Jiang, G. Song, C. Gao, Y. Wang, W. Si, and K. Xie. (2011, Aug.). Simulated annealing based influence maximization in social networks. Presented at Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. [Online]. 25(1), pp. 127–132. Available: https://doi.org/10.1609/aaai.v25i1.7838
  10. Şimşek and R. Kara. (2018, Dec.). Using swarm intelligence algorithms to detect influential individuals for influence maximization in social networks. Expert Systems with Applications. [Online]. 114, pp. 224–236. Available: https://doi.org/10.1016/j.eswa.2018.07.038
  11. D. Navaei, M. H. Rezvani, and A. M. E. Moghaddam. (2024, Feb.). A novel neighborhood-based importance measure for social network influence maximization using NSGA-III. Presented at 2024 10th International Conference on Artificial Intelligence and Robotics (QICAR), pp. 113-118. [Online]. Available: https://doi.org/10.1109/QICAR61538.2024.10496642
  12. Cui, H. Hu, S. Yu, Q. Yan, Z. Ming, Z. Wen, and N. Lu. (2018, Feb.). DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. Journal of Network and Computer Applications. [Online]. 103, pp. 119–130. Available: https://doi.org/10.1016/j.jnca.2017.12.003
  13. Tang, R. Zhang, Y. Yao, F. Yang, Z. Zhao, R. Hu, and Y. Yuan. (2019, Jan.). Identification of top-k influential nodes based on enhanced discrete particle swarm optimization for influence maximization. Physica A: Statistical Mechanics and Its Applications. [Online]. 513, pp. 477–496. Available: https://doi.org/10.1016/j.physa.2018.09.040
  14. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. (2007, Aug.). Cost-effective outbreak detection in networks. in Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420-429. [online]. Available: https://doi.org/10.1145/1281192.1281239
  15. Mokhtarizadeh, B. Zamani Dehkordi, M. Mosleh, and A. Barati. (2021, Oct.). Influence maximization using time delay based harmonic centrality in social networks. Tabriz Journal of Electrical Engineering. [Online]. pp. 359–370.
  16. Han, Q. Zhou, J. Tang, X. Yang, and H. Huang. (2021, Feb.). Identifying top-k influential nodes based on discrete particle swarm optimization with local neighborhood degree centrality. IEEE Access. [Online]. 9, pp. 21345–21356. Available: https://doi.org/10.1109/ACCESS.2021.3056087
  17. Arora, S. Bansal, C. Kandpal, R. Aswani, and Y. Dwivedi. (2019, Jul.). Measuring social media influencer index—insights from Facebook, Twitter and Instagram. Journal of Retailing and Consumer Services. [Online]. 49, pp. 86–101. Available: http://dx.doi.org/10.1016/j.jretconser.2019.03.012
  18. Fu, J. Zhang, W. Li, M. Zhang, Y. He, and Q. Mao. (2022, Jul.). A differential evolutionary influence maximization algorithm based on network discreteness. Symmetry. [Online]. 14(7), p. 1397. Available: https://doi.org/10.3390/sym14071397
  19. Chatterjee, T. Bhattacharyya, K. K. Ghosh, A. Chatterjee, and R. Sarkar. (2021, Feb.). A novel meta-heuristic approach for influence maximization in social networks. Expert Systems. [Online]. p. 12676. Available: https://doi.org/10.1111/exsy.12676
  20. Tarun K. Biswas , A. Abbasi, Ripon, K. Chakrabortty , "An MCDM integrated adaptive simulated annealing approach for influence maximization in social networks", v556, pp. 27-48, (2021). Availabe: https://doi.org/10.1016/j.ins.2020.12.048
  21. Li, R. Zhang, Z. Zhao, X. Liu, and Y. Yuan. (2021, Nov.). Identification of top-k influential nodes based on discrete crow search algorithm optimization for influence maximization. Applied Intelligence. [Online]. 51(11), pp. 7749–7765. Available: http://doi.org/10.1007/s10489-021-02283-9
  22. Cantini, F. Marozzo, S. Mazza, D. Talia, and P. Trunfio. (2021, Sep.). A weighted artificial bee colony algorithm for influence maximization. Online Social Networks and Media. [Online]. 26, p. 100167. Available: https://doi.org/10.1016/j.osnem.2021.100167
  23. Karczmarczyk, J. Jankowski, and J. Wątrobski. (2021, Jun.). Multi-criteria seed selection for targeted influence maximization within social networks. Presented at International Conference on Computational Science (ICCS 2021), pp. 454–461. [Online]. Available: https://doi.org/10.1007/978-3-030-77967-2-38
  24. Han, K. C. Li, A. Castiglione, J. Tang, H. Huang, and Q. Zhou. (2021, Apr.). A clique-based discrete bat algorithm for influence maximization in identifying top-k influential nodes of social networks. Soft Computing—A Fusion of Foundations, Methodologies & Applications. [Online]. 25(13), pp. 8223–8240. Available: https://doi.org/10.1007/s00500-021-05749-7
  25. Zhao, Z. Zhang, and L. Wang. (2020, Jan.). Manta ray foraging optimization: An effective bio-inspired optimizer for engineering applications. Engineering Applications of Artificial Intelligence. [Online]. 87, p. 103300. Available: https://doi.org/10.1016/j.engappai.2019.103300
  26. Wang, Y. Wang, Y. Wang, and Z. Wang. (2022, Oct.). Comparison of multi-objective evolutionary algorithms applied to watershed management problem. Journal of Environmental Management. [Online]. 324, p. 116255. Available: https://doi.org/10.1016/j.jenvman.2022.116255
  27. R. Singh. (2021, Aug.). Centrality measures: A tool to identify key actors in social networks. In Principles of Social Networking: The New Horizon and Emerging Challenges. [Online]. pp. 1–27. Available: https://doi.org/10.1007/978-981-16-3398-0-1
  28. Rossi and N. Ahmed. (2015, Jan.). The network data repository with interactive graph analytics and visualization. in Proceedings of the AAAI conference on artificial intelligence. [online]. Available: https://doi.org/10.1609/aaai.v29i1.9277
  29. Ghafori and F. S. Gharehchopogh. (2022, Jan.). A multiobjective Cuckoo Search Algorithm for community detection in social networks. In Multi-objective Combinatorial Optimization Problems and Solution Methods. [Online]. pp. 177–193. Available: https://doi.org/10.1016/B978-0-12-823799-1.00007-3
  30. Heydariyan, F. S. Gharehchopogh, and M. R. E. Dishabi. (2024, Jul.). A hybrid multi-objective algorithm based on slime mould algorithm and sine cosine algorithm for overlapping community detection in social networks. Cluster Computing. [Online]. 27(10), pp. 13897–13917. Available: https://doi.org/10.1007/s10586-024-04632-y
  31. Sheykhzadeh, B. Zarei, and F. S. Gharehchopogh. (2024, Jul.). Community detection in social networks using a local approach based on node ranking. IEEE Access. [Online]. 12, pp. 92892–92905. Available: https://doi:10.1109/ACCESS.2024.3420109
  32. M. Aghdam, F. S. Gharehchopogh, and M. Masdari. (2024, Mar.). A hybrid approach in opinion leaders selection using African vultures optimization and hunger games search algorithms. Social Network Analysis and Mining. [Online]. 14(1), p. 60. Available: https://doi.org/10.1007/s13278-024-01228-7
  33. M. Aghdam, F. S. Gharehchopogh, and M. Masdari. (2025, Apr.). An opinion leader selection in social networks using hybrid amended salp swarm and improved grey wolf optimizer algorithms. International Journal of Data Science and Analytics. [Online]. pp. 1–26. Available: https://doi.org/10.1007/s41060-025-00760-9
Send comment about this article
CAPTCHA Image

Files

Share

How to cite

Statistics