International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 16, No. 2, 8 Apr. 2024
Cover page and Table of Contents: PDF (size: 647KB)
Performance Evaluation of Evolutionary Algorithms on Solving the Influence Maximization Problem in Social Networks
PDF (647KB), PP.83-97
Views: 0 Downloads: 0
Author(s)
Agash Uthayasuriyan
1
Hema Chandran G
1
Kavvin UV
1
Sabbineni Hema Mahitha
1
Jeyakumar G
2,*
Index Terms
Social network, Influence Maximization, Seed nodes, Evolutionary Algorithm, Genetic Algorithm, Ant Colony Optimization, Particle Swarm Optimization, Differential Evolution
Abstract
Influence Maximization (IM) is an optimization problem that deals with identifying the most valuable individuals/ nodes present in the network to attain the maximal information spread when they are activated. Evolutionary Algorithms (EAs) inspired from nature are one of the most powerful methods to solve an optimization problem. This paper attempts to solve the IM problem using few of the popular EAs such as Genetic Algorithm (GA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and Differential Evolution (DE). These algorithm’s performance is evaluated using four comparative metrics, that deal with assessing solution quality, computational efficiency, and scalability. The experimental results of these EAs when tested on several real-world networks reveal that the GE and PSO algorithms were found to produce relatively poorer quality of seed nodes and also with higher computational costs, making it less preferrable. DE was able to obtain the best seed sets (in terms of influence spread value) than other algorithms and ACO, the fastest among all the considered algorithms in terms of execution time, was found to obtain seed set with appreciable influence spread with a slightly higher computational cost than DE.
Cite This Paper
Agash Uthayasuriyan, Hema Chandran G, Kavvin UV, Sabbineni Hema Mahitha, Jeyakumar G, "Performance Evaluation of Evolutionary Algorithms on Solving the Influence Maximization Problem in Social Networks", International Journal of Modern Education and Computer Science(IJMECS), Vol.16, No.2, pp. 83-97, 2024. DOI:10.5815/ijmecs.2024.02.07
Reference
[1]C. L. Streeter and D. F. Gillespie, ''Social network analysis,'' J. Social Service Res., vol. 16, nos. 1-2, pp. 201-222, 1993.
[2]Agash Uthayasuriyan, G. R. Ramya, and G. Jeyakumar. "Effective Link Prediction in Complex Networks Using Differential Evolution Based Extreme Gradient Boosting Algorithm." Advanced Network Technologies and Intelligent Computing: Second International Conference, ANTIC 2022, Varanasi, India, December 22–24, 2022, Proceedings, Part I. Cham: Springer Nature Switzerland, 2023. pp. 149-163.
[3]A. H. L, S, A., G, A., P, S., and Dr. Sajeev G. P., “A Proximity Based Community Detection in Temporal Graphs”, in 2020 IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT), 2020.
[4]G. R. Ramya and P. Bagavathi Sivakumar, "An incremental learning temporal influence model for identifying topical influencers on Twitter dataset", Social Network Analysis and Mining, vol. 11, no. 1, pp. 1-16, 2021.
[5]J. Cheriyan and G. P. Sajeev, "SpreadMax: A Scalable Cascading Model for Influence Maximization in Social Networks," 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Bangalore, India, 2018, pp. 1290-1296.
[6]L. Wang, L. Ma, C. Wang, N. -G. Xie, J. M. Koh and K. H. Cheong, "Identifying Influential Spreaders in Social Networks Through Discrete Moth-Flame Optimization," in IEEE Transactions on Evolutionary Computation, vol. 25, no. 6, pp. 1091-1102, Dec. 2021.
[7]L. Cui et al., “DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks,” J. Netw. Comput. Appl., vol. 103, pp. 119–130, Feb. 2018.
[8]L. Zhang, Y. Liu, F. Cheng, J. Qiu and X. Zhang, "A Local-Global Influence Indicator Based Constrained Evolutionary Algorithm for Budgeted Influence Maximization in Social Networks," in IEEE Transactions on Network Science and Engineering, vol. 8, no. 2, pp. 1557-1570.
[9]Weihua Li, Yuxuan Hu, Chenting Jiang, Shiqing Wu, Quan Bai, Edmund Lai, “ABEM: An adaptive agent-based evolutionary approach for influence maximization in dynamic social networks”, Applied Soft Computing, Vol. 136, 110062, ISSN 1568 – 4946.
[10]C. Wang, J. Zhao, L. Li, L. Jiao, J. Liu and K. Wu, "A Multi-Transformation Evolutionary Framework for Influence Maximization in Social Networks," in IEEE Computational Intelligence Magazine, vol. 18, no. 1, pp. 52-67.
[11]D.-L. Nguyen, T.-H. Nguyen, T.-H. Do, and M. Yoo, “Probability- based multi-hop diffusion method for influence maximization in social networks,” Wireless Pers. Commun., vol. 93, no. 4, pp. 903–916, Apr. 2017.
[12]A. Zareie, A. Sheikhahmadi, and M. Jalili, “Identification of influential users in social network using gray wolf optimization algorithm,” Exp. Syst. Appl., vol. 142, Mar. 2020, Art. no. 112971.
[13]P. Surekha, P. Mohanaraajan, R. A., and Sumathi, S., “Ant Colony Optimization for Solving Combinatorial Fuzzy Job Shop Scheduling Problems”, Int. Conf. on Communication and Computational Intelligence. Kongu Engineering College, Erode, India, 2010.
[14]Jayakumar V. and Raju, R., “A multi-objective genetic algorithm approach to the probabilistic manufacturing cell formation problem”, South African Journal of Industrial Engineering, vol. 22, no. 1, pp. 199-212, 2011.
[15]F. Riquelme, P. Gonzalez-Cantergiani, X. Molinero, and M. Serna, "Centrality measure in social networks based on linear threshold model," Knowl.-Based Syst., vol. 140, pp. 92-102, 2018.
[16]P. Li, K. Liu, K. Li, J. Liu, and D. Zhou, "Estimating user influence ranking in independent cascade model," Physica A, Stat. Mech. Appl., vol. 565, 2021, Art. no. 125584.
[17]W. Chen, W. Lu, and N. Zhang, "Time-critical influence maximization in social networks with time-delayed diffusion process," in Proc. AAAI Conf. Artif. Intell., Toronto, Ontario, Canada, AAAI, 2012, vol. 26, no. 1, pp. 592-598.
[18]J.-R. Lee and C.-W. Chung, “A fast approximation for influence maximization in large social networks,” in Proc. 23rd Int. Conf. World Wide Web, Seoul, Republic of Korea, ACM, 2014, pp. 1157–1162.
[19]S. Mirjalili, ‘‘Genetic algorithm,’’ in Evolutionary Algorithms and Neural Networks. Cham, Switzerland: Springer, 2019, pp. 43–55.
[20]Dhanalakshmy, D.M., Akhila, M.S., Vidhya, C.R., Jeyakumar, G.: Improving the search efficiency of differential evolution algorithm by population diversity analysis and adaptation of mutation step sizes. Int. J. Adv. Intell. Paradig. 15(2), 119–145 (2020).
[21]Simpson, A. R. Maier, H. R., Foong, W. K., Phang, K. Y., Seah, H. Y., and Tan, C. L., 2001, ‘Selection of parameters for ant colony optimization applied to the optimal design of water distribution systems’, in Proc., Int. Congress on Modeling and Simulation. Canberra, Australia, pp. 1931– 1936.
[22]Alan Piszcz, Terence Soule, (2006) "Genetic Programming: Analysis of Optimal Mutation Rates in a Problem with Varying Difficulty", in the proceedings of Artificial Intelligence Research Society Conference, vol.19. Flairs, Florida, pp.451-456,2006.
[23]Kunegis, J.: KONECT—the Koblenz network collection. In: Proceedings of the 22nd International Conference on World Wide Web, pp. 1343–1350 (2013).
[24]Z. Liang, Q. He, H. Du and W. Xu, "Targeted influence maximization in competitive social networks", Information Sciences, vol. 619, pp. 390-405, 2023.
[25]Zareie, A., Sakellariou, R. Influence maximization in social networks: a survey of behaviour-aware methods. Soc. Netw. Anal. Min. 13, 78 (2023).