Volume 20, Issue 3 (12-2023)
JSDP 2023, 20(3): 47-60 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Deypir M, Bayat E. Identifying Community Structures in Social Networks using Discrete Harmony Search Algorithm. JSDP 2023; 20 (3) : 4
URL: http://jsdp.rcisp.ac.ir/article-1-1295-en.html
URL: http://jsdp.rcisp.ac.ir/article-1-1295-en.html
Abstract: (648 Views)
Nowadays, social networks play an important role in people's daily lives. A social network is a kind of social structure that consists of several nodes that can be individuals or organizations. Most importantly, these nodes are connected by one or more specific types of dependencies, such as friendships or work relationships. Understanding the structure and constituent groups of these networks can give us useful information about the state of society and individuals. In this article, a new solution to solve the problem of social structure detection is provided. Social structure means communities or associations in social networks. An important issue of this context is network graph construction based on objects as nodes and edges as transactions between these objects. Community detection is based on these graphs. The appropriate solution is to identify and create clusters of nodes that have strong connections with each other and at the same time have weaker connections between nodes of different clusters. Optimization algorithms can be used to construct and detect these connections. Harmonic search is one of the efficient optimization algorithms in this context. However, in the field of identifying communication structures and communities, so far, no research work has been done using the harmonic search algorithm. In this paper, a new method is proposed to construct network clusters based on network graphs. It can identify effective communications based on different criteria. In order to propose this method, first a new version of harmonic search algorithm is designed for discrete environments while the original version of which is for continuous environments. Then, according the problem, which is to discover appropriate structures in the social network graph, a new method is devised to solve it. This method tries to provide a suitable discrete version by relying on different operators to be applicable to solve the desired problem. In order to evaluate the proposed method, various experiments were carried out on several different networks. These networks have been used as benchmark in previous research work. For evaluation and comparison, two artificial networks and two real networks are considered. The evaluation results of the proposed method on these networks are presented based on different criteria and compared with four previous algorithms that are known in this field. Comparison results show that the proposed algorithm is relatively superior to other algorithms or at least produces similar results. The most important reason that can justify the relative performance superiority of the proposed algorithm or at least its competitive results is the better search capability of the problem search space. This leads to the discovery of more promising points and the production of better solutions.
Article number: 4
Keywords: Social network, Network graph, Community detection, Harmony search optimization algorithm.
Type of Study: Research |
Subject:
Paper
Received: 2022/02/3 | Accepted: 2023/02/22 | Published: 2024/01/14 | ePublished: 2024/01/14
Received: 2022/02/3 | Accepted: 2023/02/22 | Published: 2024/01/14 | ePublished: 2024/01/14
References
1. [1] L. Wang, Y. Xu, Y. Mao, M. Fei, "A Discrete Harmony Search Algorithm," LSMS/ICSEE 2010, Part II, CCIS 98, © Springer-Verlag Berlin Heidelberg, pp. 37-43, 2010.
2. [2] M.Girvan, and M.E.J. "Newman, Community structure in social and biological networks," Proc. Natl. Acad. Sci. USA 99 (12): Doi: 10.1073/pnas.122653799. 2002, pp. 7821-7826. [DOI:10.1073/pnas.122653799] [PMID] []
3. [3] S. Fortunato, "Community detection in graphs," Physics Reports 486, pp. 75-174. 2010.
4. [4] K. Steinhaeuser, N.V. Chawla, "Identifying and evaluating community structure in complex networks," Pattern Recognition Letters, Vol. 31, Issue 5, pp. 413-421, 2010.
5. [5] Q. Cai, M. Gong, B. Shen, L. Ma, L. Jiao, "Discrete Particle Swarm Optimization for Identifying Community Structures in Signed Social Networks," 2014.
6. [6] J. Kennedy, R. Eberhart, "Particle swarm optimization," In: Proceedings of 1995 IEEE International Conference on Neural Networks. Vol. 4. pp. 1942-1948, 1995.
7. [7] F. D., Malliaros, M. Vazirgiannis, "Clustering and community detection in directed networks: A survey," Phys. Rep. 533 (4): 95-142, 2013.
8. [8] Z.W., Geem," A New Heuristic Optimization Algorithm: Harmony Search," Simulation, Springer-Verlag Berlin Heidelberg, vol. 76, no. 2, pp. 60-68, 2001.
9. [9] K. S. Lee, Z. W. Geem, "A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice," Computer Methods in Applied Mechanics and Engineering, vol. 194, pp. 3902-3933, 2004.
10. [10] Z. W. Geem, "Music-Inspired Harmony Search Algorithm, Theory and Applications," Springer-Verlag Berlin Heidelberg, Vol. 191, 2009.
11. [11] M. A. Porter, J. P. Onnela, P.J. Mucha, "Communities in Networks," Not. Amer. Math. Soc. Vol. 56(9): pp. 1082-1097, 2009.
12. [12] M.E.J. Newman, "Fast algorithm for detecting community structure in networks," Phys. Rev. E 69 (6): 066133. 2004.
13. [13] M. E. J. Newman, "Detecting community structure in networks," Eur. Phys. J. B Vol. 38 (2): pp. 321-330, 2004.
14. [14] A. Lancichinetti, S. Fortunato, and F. Radicchi, "Benchmark graphs for testing community detection algorithms," Phys. Rev. E, Vol. 78 (4): 046110, 2008.
15. [15] Bo, Yang, K. William Cheung, and L. Jiming, "Community mining from signed social networks," Knowledge and Data Engineering, IEEE transactions on knowledge and data engineering, Vol. 19(10), 1333-1348, 2007.
16. [16] A. Ferligoj, and A. Kramberger, "An analysis of the slovene parliamentary parties network," Developments in statistics and methodology, pp.209-216, 1996.
17. [17] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon, "Network motifs: simple building blocks of complex networks," Science, 298(5594), pp. 824-827, 2002.
18. [18] K. Oda, T. Kimura, Y. Matsuoka, A. Funahashi, A., M. Muramatsu, and H. Kitano, "Molecular interaction map of a macrophage," AfCS Research Reports, 2(14), pp. 1-12, 2004.
19. [19] K. Oda, Y. Matsuoka, A. Funahashi, and H. Kitano, "Comprehensive pathway map of epidermal growth factor receptor signaling," Molecular systems biology, 1(1), pp. 2005-0010, 2005.
20. [20] E. Read, Kenneth. "Cultures of the central highlands, New Guinea."Southwestern Journal of Anthropology: pp. 1-43, 1954.
21. [21] S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, "Network motifs in the transcriptional regulation network of Escherichia coli," Nature genetics, 31(1), pp. 64-68, 2002.
22. [22] C. Pizzuti, "Ga-net: A genetic algorithm for community detection in social networks," In International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Heidelberg, September 2008, pp. 1081-1090.
23. [23] C. Shi, Z. Yan, Y. Cai, and B. Wu, "Multi-objective community detection in complex networks," Applied Soft Computing, 12(2), pp. 850-859, 2012.
24. [24] M. Gong, Q. Cai, X. Chen, and L. Ma, "Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition," IEEE Transactions on Evolutionary Computation, 18(1), pp. 82-97, 2014.
25. [25] Z. Li, L. He, and Y. Li, "A novel multiobjective particle swarm optimization algorithm for signed network community detection," Applied Intelligence, 44(3), pp. 621-633, 2016.
26. [26] S. Gómez, P. Jensen, and A. Arenas, "Analysis of community structure in networks of correlated data," Physical Review E, 80(1), 016114, 2009.
27. [27] Y. Su, B. Wang, F. Cheng, L. Zhang, X. Zhang, and L. Pan, "An algorithm based on positive and negative links for community detection in signed networks," Scientific Reports, 7(1), 10874, 2017.
28. [28] K. R.. Žalik, , and B. Žalik, "Multi-objective evolutionary algorithm using problem-specific genetic operators for community detection in networks," Neural Computing and Applications, pp. 1-14, 2017.
29. [29] C. Pizzuti, "Evolutionary computation for community detection in networks: a review," IEEE Transactions on Evolutionary Computation, 22(3), pp. 464-483, 2018.
30. [30] Y. Atay, I. Koc, I. Babaoglu, and H. Kodaz, "Community detection from biological and social networks: A comparative analysis of metaheuristic algorithms," Applied Soft Computing, 50, pp.194-211, 2017.
31. [31] Y. Dong, M. Luo; J. Li, D. Cai, Q. Zheng, "LookCom: Learning Optimal Network for Community Detection," IEEE Transactions on Knowledge and Data Engineering, 34(2), pp. 764 - 775, 2022.
32. [32] L Wu, Q Zhang, CH Chen, K Guo, D Wang ," Deep learning techniques for community detection in social networks," IEEE Access, 8, pp. 96016 - 96026, 2020.
33. [33] S Li, L Jiang, X Wu, W Han, D Zhao, Z Wang, "A weighted network community detection algorithm based on deep learning," Applied Mathematics and Computation, 401(15), p.126012, 2021.
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
