* Corresponding Author
Hide
Show all
Determining Community Structure and Modularity in Social Network using Genetic Algorithm
https://doi.org/10.22146/ijccs.57834 Taufan Bagus Dwi Putra Aditama(1*), Azhari SN(2)
(1) Master Program of Computer Science, FMIPA UGM, Yogyakarta
(2) Department of Computer Science and Electronics, FMIPA UGM, Yogyakarta
(*) Corresponding Author
Abstract
Research on determining community structure in complex networks has attracted a lot of attention in various applications, such as email networks and social networks. The popularity determines the structure of a community because it can analyze the structure.
Meanwhile, to determine the structure of the community by maximizing the value of modularity is difficult. Therefore, a lot of research introduces new algorithms to solve problems in determining community structure and maximizing the value of modularity. Genetic Algorithm can provide effective solutions by combining exploration and exploitation.
This study focuses on the Genetic Algorithm which added a cleanup feature in the process. The final results of this study are the results of a comparison of modularity values based on the determination of the community structure of the Genetic Algorithm, Girvan and Newman Algorithm, and the Louvain Algorithm. The best modularity values were obtained using the Genetic Algorithm which obtained 0.6833 results for Zachary's karate club dataset, 0.7446 for the Bottlenose dolphins dataset, 0.7242 for the American college football dataset, and 0.5892 for the Books about US politics dataset.
Keywords
Full Text:
PDFReferences
[1] J. Zhang, X. Ding, and J. Yang, “Revealing the role of node similarity and community merging in community detection,” Knowledge-Based Systems, vol. 165, pp. 407–419, Feb. 2019.
[2] X. Chen and J. Li, “Community detection in complex networks using edge-deleting with restrictions,” Physica A: Statistical Mechanics and its Applications, vol. 519, pp. 181–194, Apr. 2019.
[3] H. Jin, W. Yu, and S. Li, “Graph regularized nonnegative matrix tri-factorization for overlapping community detection,” Physica A: Statistical Mechanics and its Applications, vol. 515, pp. 376–387, Feb. 2019.
[4] E. Jokar and M. Mosleh, “Community detection in social networks based on improved Label Propagation Algorithm and balanced link density,” Physics Letters A, vol. 383, no. 8, pp. 718–727, Feb. 2019.
[5] Y. Xu, “Community detection based on network communicability distance,” Physica A: Statistical Mechanics and its Applications, vol. 515, pp. 112–118, Feb. 2019.
[6] X. Zhou, K. Yang, Y. Xie, C. Yang, and T. Huang, “A novel modularity-based discrete state transition algorithm for community detection in networks,” Neurocomputing, vol. 334, pp. 89–99, Mar. 2019.
[7] M. Arasteh and S. Alizadeh, “A fast divisive community detection algorithm based on edge degree betweenness centrality,” Appl Intell, vol. 49, no. 2, pp. 689–702, Feb. 2019.
[8] Y. Lei, Y. Zhou, and J. Shi, “Overlapping communities detection of social network based on hybrid C-means clustering algorithm,” Sustainable Cities and Society, vol. 47, p. 101436, May 2019.
[9] H. S. Pattanayak, A. L. Sangal, and H. K. Verma, “Community detection in social networks based on fire propagation,” Swarm and Evolutionary Computation, vol. 44, pp. 31–48, Feb. 2019.
[10] M. Lu, Z. Qu, Z. Wang, and Z. Zhang, “Hete_MESE: Multi-Dimensional Community Detection Algorithm Based on Multiplex Network Extraction and Seed Expansion for Heterogeneous Information Networks,” IEEE Access, vol. 6, pp. 73965–73983, 2018.
[11] B. Rao, A. Mitra, and J. Mondal, “Algorithm for Retrieval of Sub-community Graph from a Compressed Community Graph Using Graph Mining Techniques,” Procedia Computer Science, vol. 57, pp. 678–685, 2015.
[12] H. Liu, F. Yang, and D. Liu, “Genetic algorithm optimizing modularity for community detection in complex networks,” in 2016 35th Chinese Control Conference (CCC), Chengdu, China, Jul. 2016, pp. 1252–1256.
[13] B. S. Khan and M. A. Niazi, “Network Community Detection: A Review and Visual Survey,” p. 39, 2017.
[14] G. Gadek, A. Pauchet, N. Malandain, K. Khelif, L. Vercouter, and S. Brunessaux, “Topical cohesion of communities on Twitter,” Procedia Computer Science, vol. 112, pp. 584–593, 2017.
[15] A. F. Hidayatullah and Azhari SN, “Analisis Sentimen dan klasifikasi kategori terhadap tokoh publik pada data Twitter menggunakan Naive Bayes Classifier,” Universitas Gadjah Mada, 2014.
[16] A. Chianese and F. Piccialli, “A Service Oriented Framework for Analysing Social Network Activities,” Procedia Computer Science, vol. 98, pp. 509–514, 2016.
[17] S. Guesmi, C. Trabelsi, and C. Latiri, “CoMRing: A Framework for Community Detection Based on Multi-relational Querying Exploration,” Procedia Computer Science, vol. 96, pp. 627–636, 2016.
[18] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. Cambridge, MA, USA: MIT Press, 1992.
[19] A. A. AbdulHamed, M. A. Tawfeek, and A. E. Keshk, “A genetic algorithm for service flow management with budget constraint in heterogeneous computing,” Future Computing and Informatics Journal, vol. 3, no. 2, pp. 341–347, Dec. 2018.
[20] A. Amirjanov, “Modeling the Dynamics of a Changing Range Genetic Algorithm,” Procedia Computer Science, vol. 102, pp. 570–577, 2016.
[21] M. Imran, N. A. Pambudi, and M. Farooq, “Thermal and hydraulic optimization of plate heat exchanger using multi objective genetic algorithm,” Case Studies in Thermal Engineering, vol. 10, pp. 570–578, Sep. 2017.
[22] K. Jankauskas, L. G. Papageorgiou, and S. S. Farid, “Fast genetic algorithm approaches to solving discrete-time mixed integer linear programming problems,” Computers & Chemical Engineering, vol. 121, pp. 212–223, Feb. 2019.
[23] G. Nagarajan, R. I. Minu, B. Muthukumar, V. Vedanarayanan, and S. D. Sundarsingh, “Hybrid Genetic Algorithm for Medical,” Procedia Computer Science, vol. 85, pp. 455–462, 2016.
[24] P. Rai, A. Agrawal, M. L. Saini, C. Jodder, and A. G. Barman, “Volume optimization of helical gear with profile shift,” Procedia Computer Science, vol. 133, pp. 718–724, 2018.
[25] M. Vizcaíno-González, J. Pineiro-Chousa, and M. Á. López-Cabarcos, “Analyzing the determinants of the voting behavior using a genetic algorithm,” European Research on Management and Business Economics, vol. 22, no. 3, pp. 162–166, Sep. 2016.
[26] M. Tasgin and H. Bingol, “Community Detection in Complex Networks using Genetic Algorithm,” Apr. 2006.
[27] G. Jia et al., “Community Detection in Social and Biological Networks Using Differential Evolution,” in Learning and Intelligent Optimization, vol. 7219, Y. Hamadi and M. Schoenauer, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 71–85.
[28] M. B. M’Barek, A. Borgi, W. Bedhiafi, and S. B. Hmida, “Genetic Algorithm for Community Detection in Biological Networks,” Procedia Computer Science, vol. 126, pp. 195–204, 2018.
[29] W. W. Zachary, “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, vol. 33, no. 4, pp. 452–473, 1977.
[30] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, “The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations,” Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396–405, Sep. 2003.
[31] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, Jun. 2002.
[32] M. E. J. Newman, “Modularity and community structure in networks,” Proceedings of the National Academy of Sciences, vol. 103, no. 23, pp. 8577–8582, Jun. 2006.
[33] I. A. Hadi, “Pentingnya Pengenalan Tentang Perbedaan Individu Anak Dalam Efektifitas Pendidikan,” INSPIRASI: Jurnal Kajian dan Penelitian Pendidikan Islam, vol. 1, no. 1, pp. 71–92, May 2017.
[34] M. Negnevitsky, Artificial intelligence: a guide to intelligent systems, 2nd ed. Harlow, England ; New York: Addison-Wesley, 2005.
[35] E. Suhartono, “Optimasi Penjadwalan Mata Kuliah Dengan Algoritma Genetika (Studi Kasus di AMIK JTC Semarang),” INFOKAM, vol. 11, no. 5, Dec. 2015.
[36] A. Rianawati and W. F. Mahmudy, “Implementasi Algoritma Genetika Untuk Optimasi Komposisi Makanan Bagi Penderita Diabetes Mellitus,” vol. 5, no. 14, p. 12, 2015.
[37] I. M. B. Adnyana and N. K. D. A. Jayanti, “Implementasi Sistem Penjadwalan Ujian Akhir Semester menggunakan Algoritma Genetika,” CSRID, vol. 6, no. 1, pp. 11–20, Oct. 2015.
[38] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Phys. Rev. E, vol. 74, no. 3, p. 036104, Sep. 2006.
[39] M. B. Bashir and A. Nadeem, “Improved Genetic Algorithm to Reduce Mutation Testing Cost,” IEEE Access, vol. 5, pp. 3657–3674, 2017.
[40] M. Gen, R. Cheng, and L. Lin, Network models and optimization: multiobjective genetic algorithm approach. London: Springer, 2008.
[41] D. E. Goldberg and R. Lingle Jr., “AllelesLociand the Traveling Salesman Problem,” in Proceedings of the 1st International Conference on Genetic Algorithms, Hillsdale, NJ, USA, 1985, pp. 154–159.
[42] I. Iryanto and E. Ismantohadi, “Optimasi Pemilihan Barang Dagangan bagi Pedagang Keliling dengan Algoritma Genetika,” JTT (Jurnal Teknologi Terapan), vol. 3, no. 1, pp. 24-28–28, Mar. 2017.
[43] V. Kumar S G and R. Panneerselvam, “A Study of Crossover Operators for Genetic Algorithms to Solve VRP and its Variants and New Sinusoidal Motion Crossover Operator,” International Journal of Computational Intelligence Research, vol. 13, pp. 1717–1733, 2017.
[44] A. B. A. Hassanat and E. Alkafaween, “On Enhancing Genetic Algorithms Using New Crossovers,” p. 15, 2018.
[45] E. Raju, M. A. Hameed, and K. Sravanthi, “Detecting communities in social networks using unnormalized spectral clustering incorporated with Bisecting K-means,” in 2015 IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT), pp. 1–5.
[46] A. Malathi and D. Radha, “Analysis and visualization of social media networks,” in 2016 International Conference on Computation System and Information Technology for Sustainable Solutions (CSITSS), Oct. 2016, pp. 58–63.
DOI: https://doi.org/10.22146/ijccs.57834
Article Metrics
Abstract views : 3701
| 
views : 3069
Refbacks
- There are currently no refbacks.
Copyright (c) 2020 IJCCS (Indonesian Journal of Computing and Cybernetics Systems)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
View My Stats1