An Elitism-based Novel Approach for Community Detection in Social Networks
DOI:
https://doi.org/10.52756/ijerr.2024.v46.027Keywords:
Genetic algorithm, Elitism, Modularity, Community detection, Social networks, Multi-objective, Swarm-intelligent techniques, Convergence, Local optimaAbstract
The detection of communities is an important problem in social network analysis, which has applications in various domains like sociology, biology, computer science, and marketing. In this context, genetic algorithms have proven to be effective in detecting communities by optimizing the modularity score of the network. The proposed work in this research paper uses an elitism-based genetic algorithm with some modified crossover and mutation techniques to detect communities in social networks. The proposed methodology incorporates the concepts of elitism, N-point crossover, and inverse mutation to enhance the effectiveness of genetic algorithms in solving optimization problems. The idea introduced in this article significantly extends the current understanding of optimization and evolutionary algorithms. We present an advanced methodology that leverages various genetic operators to improve the performance of a genetic algorithm in solving community detection problems in complex networks. Numerous research papers have extensively showcased the practicality of evolutionary and swarm-based algorithms in addressing real-world problems across diverse domains like viral marketing, link prediction, influence maximization, political polarization, etc. Hybridizing these algorithms with other optimization techniques has improved the performance and convergence speed, leading to enhanced optimization outcomes.
References
A.J., U., & P.D., S. (2015). Crossover operators in genetic algorithms: A review. ICTACT Journal on Soft Computing, 6(1), 1083–1092. https://doi.org/10.21917/ijsc.2015.0150
Audet, C., & Hare, W. (2017). Genetic Algorithms. Derivative-Free and Blackbox Optimization, pp. 57–73. https://doi.org/10.1007/978-3-319-68913-5_4
Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008. https://doi.org/10.1088/1742-5468/2008/10/P10008
Camacho, D., Panizo-LLedot, Á., Bello-Orgaz, G., Gonzalez-Pardo, A., & Cambria, E. (2020). The four dimensions of social network analysis: An overview of research methods, applications, and software tools. Information Fusion, 63, 88–120. https://doi.org/10.1016/j.inffus.2020.05.009
Che, S., Yang, W., & Wang, W. (2021). An improved artificial bee colony algorithm for community detection in bipartite networks. IEEE Access, 9, 10025–10040. https://doi.org/10.1109/ACCESS.2021.3050752
Chen, Z., Liu, F., Gao, C., Li, X., & Zhang, Z. (2017). An enhanced particle swarm optimization based on Physarum model for community detection. Lecture Notes in Computer Science, 10386, 99–108. https://doi.org/10.1007/978-3-319-61833-3_11
Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5), 75-174. https://doi.org/10.1016/j.physrep.2009.11.002
Guariso, G., & Sangiorgio, M. (2020). Improving the performance of multiobjective genetic algorithms: An elitism-based approach. Information, 11(12), 1–14. https://doi.org/10.3390/info11120587
Guo, X., Su, J., Zhou, H., Liu, C., Cao, J., & Li, L. (2019). Community detection based on genetic algorithm using local structural similarity. IEEE Access, 7, 134583-134600. https://doi.org/10.1109/ACCESS.2019.2939864
Guo, Y., Li, X., Tang, Y., & Li, J. (2017). Heuristic artificial bee colony algorithm for uncovering community in complex networks. Mathematical Problems in Engineering, 2017, 4143638. https://doi.org/10.1155/2017/4143638
Hafez, A. I., Zawbaa, H. M., Hassanien, A. E., & Fahmy, A. A. (2014). Networks community detection using artificial bee colony swarm optimization. Advances in Intelligent Systems and Computing, 303, 229–239. https://doi.org/10.1007/978-3-319-08156-4_23
Hajipour, V., Tavana, M., Santos-arteaga, F. J., Alinezhad, A., & Di Caprio, D. (2020). An efficient controlled elitism non-dominated sorting genetic algorithm for multi-objective supplier selection under fuzziness. Journal of Computational Design and Engineering, pp. 469–488. https://doi.org/10.1093/jcde/qwaa039
He, D., Liu, J., Liu, D., Jin, D., & Jia, Z. (2011). Ant colony optimization for community detection in large-scale complex networks. Proceedings of the 2011 7th International Conference on Natural Computation (ICNC), 2, 1151–1155. https://doi.org/10.1109/ICNC.2011.6022234
Hruschka, E. R., Campello, R. J. G. B., Freitas, A. A., & de Carvalho, A. C. P. L. F. (2009). A survey of evolutionary algorithms for clustering. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 39(2), 133–155. https://doi.org/10.1109/TSMCC.2008.2007252
Huang, S., Tsai, Y. C., & Chou, F. D. (2023). A trajectory-based immigration strategy genetic algorithm to solve a single-machine scheduling problem with job release times and flexible preventive maintenance. Algorithms, 16(4). https://doi.org/10.3390/a16040207
Jaradat, A. S., & Hamad, S. B. (2018). Community structure detection using firefly algorithm. International Journal of Applied Metaheuristic Computing, 9(4), 52–70. https://doi.org/10.4018/IJAMC.2018100103
Jia, G., et al. (2012). Community detection in social and biological networks using differential evolution. Lecture Notes in Computer Science, 7219, 71–85. https://doi.org/10.1007/978-3-642-34413-8_6
Krouska, A., Troussas, C., & Sgouropoulou, C. (2023). A novel group recommender system for domain-independent decision support customizing a grouping genetic algorithm. User Modeling and User-Adapted Interaction. https://doi.org/10.1007/s11257-023-09360-3
Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4). https://doi.org/10.1103/PhysRevE.78.046110
Liu, C., & Liu, Q. (2018). Community detection based on differential evolution using modularity density. Information, 9(9). https://doi.org/10.3390/info9090218
Malhotra, D. (2021). Community detection in complex networks using link strength-based hybrid genetic algorithm. SN Computer Science, 2(1). https://doi.org/10.1007/s42979-020-00389-4
Natesha, B. V., & Guddeti, R. M. R. (2021). Adopting elitism-based genetic algorithm for minimizing multi-objective problems of IoT service placement in fog computing environment. Journal of Network and Computer Applications, 178, 102972. https://doi.org/10.1016/j.jnca.2020.102972
Osaba, E., et al. (2018). Community detection in weighted directed networks using nature-inspired heuristics. Lecture Notes in Computer Science, 11315. Springer International Publishing. https://doi.org/10.1007/978-3-030-03496-2_36
Panizo-LLedot, A., Bello-Orgaz, G., & Camacho, D. (2020). A multi-objective genetic algorithm for detecting dynamic communities using a local search driven immigrant’s scheme. Future Generation Computer Systems, 110, 960–975. https://doi.org/10.1016/j.future.2019.10.041
Pizzuti, C. (2008). GA-Net: A genetic algorithm for community detection in social networks. Lecture Notes in Computer Science (including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5199 LNCS, 1081–1090. https://doi.org/10.1007/978-3-540-87700-4_107
Pizzuti, C. (2009, November). A multi-objective genetic algorithm for community detection in networks. In 2009 21st IEEE International Conference on Tools with Artificial Intelligence, pp. 379-386. https://doi.org/ 10.1109/ICTAI.2009.58
Pizzuti, C. (2017). Evolutionary computation for community detection in networks: A review. IEEE Transactions on Evolutionary Computation, 22(3), 464-483. https://doi.org/10.1109/TEVC.2017.2737600
Putera, V. S., Permana, R. H., & Sirodj, D. A. N. (2023). Is the Indonesian Government Islamophobic? Studies Using Social Network Analysis. KnE Social Sciences, pp. 1397-1408. https://doi.org/10.18502/kss.v8i18.14342
Rahimi, S., Abdollahpouri, A., & Moradi, P. (2017). SC. Swarm and Evolutionary Computation. https://doi.org/10.1016/j.swevo.2017.10.009
Shakya, H. K., Singh, K., More, Y. S., & Biswas, B. (2022). Opposition-based genetic algorithm for community detection in social networks. Proceedings of the National Academy of Sciences of India, Section A-Physical Sciences, 92(2), 251–263. https://doi.org/10.1007/s40010-020-00716-7
Sharma, S., & Shakya, H. K. (2022). Hybrid real-time implicit feedback SOM-based movie recommendation systems. In International Conference on Computing, Communications, and Cyber-Security, pp. 371–388. Springer Nature Singapore. https://doi.org/10.1007/978-981-99-1479-1_28
Sharma, S., & Shakya, H. K. (2022, October). Hybrid real-time implicit feedback SOM-based movie recommendation systems. In International Conference on Computing, Communications, and Cyber-Security, pp. 371–388. Springer Nature Singapore. https://doi.org/10.1007/978-981-99-1479-1_28
Sharma, S., & Shakya, H. K. (2024). Hybrid recommendation system for movies using artificial neural network. Expert Systems with Applications, 258, 125194. https://doi.org/10.1016/j.eswa.2024.125194
Sharma, S., Dubey, G. P., & Shakya, H. K. (2024). Optimizing user satisfaction in movie recommendations using variable learning rates and dynamic neighborhood functions in SOMs. International Journal of Experimental Research and Review, 41(spl.), 130–145. https://doi.org/10.52756/ijerr.2024.v41spl.011
Sharma, S., Dubey, G. P., & Shakya, H. K. (2024). Reducing cluster overlap in movie recommendations with IKSOM and silhouette clustering. International Journal of Experimental Research and Review, 42, 169–182. https://doi.org/10.52756/ijerr.2024.v42.015
Sharma, S., Dubey, G. P., Shakya, H. K., & Motwani, D. (2023). Hybrid filtering methods in movie recommendation: The enhanced SOM approach. In International Conference on Information Systems and Management Science, pp. 174–187. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-70789-6_14
Sharma, S., Prasad, G., Kumar, H., & Sharma, A. (2024). SOM and hybrid filtering: Pioneering next-gen movie recommendations in the entertainment industry. Journal of Fusion: Practical Applications, 16(2), 43–62. https://doi.org/10.54216/FPA.160204
Sharma, S., Shakya, H. K., & Marriboyina, V. (2021). A location-based novel recommender framework of user interest through data categorization. Materials Today: Proceedings, 47, 7155–7161. https://doi.org/10.1016/j.matpr.2021.06.325
Tasgin, M., & Bingol, H. (2006). Community detection in complex networks using genetic algorithm. Retrieved from http://arxiv.org/abs/cond-mat/0604419
Triwiyatno, A., & Setiawan, I. (2023). Optimization of wind farm yaw offset angle using online genetic algorithm with a modified elitism strategy to maximize power production. Journal of Information Technology and Electrical Engineering, 9(1), 185–199. https://doi.org/10.26555/jiteki.v9i1.25747
Uthayasuriyan, A., G, H. C., Uv, K., Mahitha, S. H., & Jeyakumar, G. (2023). A comparative study on genetic algorithm and reinforcement learning to solve the traveling salesman problem. Research Article in Special Issue: Selected Papers from the 4th International Conference on Machine Learning, Image Processing, Network Security, and Data, 1–12. https://doi.org/10.37256/rrcs.2320232642
Wang, Z., Zhao, X., Wen, P., Xue, J., & Hu, C. (2016). Community detection in complex networks using improved artificial bee colony algorithm. Proceedings of CIMNS-16, 283–288. https://doi.org/10.2991/cimns-16.2016.71
Xiao, J., Zhang, Y. J., & Xu, X. K. (2018). Convergence improvement of differential evolution for community detection in complex networks. Physica A: Statistical Mechanics and Its Applications, 503, 762–779. https://doi.org/10.1016/j.physa.2018.02.072
Zhang, Y., Liu, Y., Li, J., Zhu, J., Yang, C., Yang, W., & Wen, C. (2020). WOCDA: A whale optimization-based community detection algorithm. Physica A: Statistical Mechanics and Its Applications, 539, 122937. https://doi.org/10.1016/j.physa.2019.122937
Zhou, D., Du, J., & Arai, S. (2023). Efficient Elitist Cooperative Evolutionary Algorithm for Multi-Objective Reinforcement Learning. IEEE Access, 11, 43128–43139. https://doi.org/10.1109/access.2023.3272115
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 International Academic Publishing House (IAPH)
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
