Community Detection in Complex Networks Using Learning Automata

Document Type : Persian Original Article

Authors

1 Electrical and Computer Engineer Faculty, University of Kashan, Kashan, Iran

2 Electrical and Computer Engineer Faculty, University of Kashan, Kashan, Iran.

Abstract

Social networks are one of the types of complex networks. Identifying communities in social networks is an effective way to use their information, for which several algorithms have been presented so far. In this paper, novel algorithms are designed, in which a learning automaton is attached to each node; The number of actions of learning automata is fixed and equal to the estimate of the number of network communities. At each step, each of the learning automata chooses an action from its set of actions. Choosing any of these actions means assigning the label of that community to the node. The action chosen by each automaton is evaluated based on the chosen actions of its neighbors ((local attention) and/or communities detected by the entire method (global screening). The result of the evaluation leads to generate rewards or punish signal for the automata. By receiving a reward, the probability of re-choosing the chosen action by the automaton, or the community label, increases, and otherwise, by receiving a fine, the probability of this action decreases. By repeating the algorithm, the optimal action is determined as long as no change occurs in the selected label of the corresponding automata of each node with more iterations, and as a result, the optimal communities are determined as the output of the algorithm. The comparison of the results of the experiments shows the effectiveness of the proposed methods in comparison with the previous methods.

Keywords

References

[1] A. Rezvanian, M. Rahmati, and M. R. Meybodi, “Sampling from complex networks using distributed learning automata,” Physica A: Statistical Mechanics and its Applications, vol. 396. pp. 224–234, 2014.
[2] R. Albert and A. L. Barabási, “Statistical mechanics of complex networks,” Reviews of Modern Physics, vol. 74, no. 1, pp. 47–97, 2002.
[3]  R. Rabbany, M. Takaffoli, J. Fagnan, O. R. Zaïane, and R. J. G. B. Campello, “Communities validity: methodical evaluation of community mining algorithms,” Social Network Analysis and Mining, vol.3, pp.1039-1062, 2013.
[4]  B. Krishnamurthy and J. Wang, “On network-aware clustering of Web clients,” Computer Communication Review, vol.30, pp. 97-110, 2000.
[5] S. Fortunato and M. Barthé, “Resolution limit in community detection,” Proceedings of the National Academy of Sciences of the United States of America, vol.104, no.1, pp. 36-41, 2007.
[6] M. A. L. Thathachar and P. S. Sastry, “Varieties of learning automata: An overview,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 32, no. 6. pp. 711–722, 2002.
[7] J. Kim and T. Wilhelm, “What is a complex graph?” Physica A: Statistical Mechanics and its Applications. vol. 387, no. 11, pp. 2637–2652, 2008.
[8] T. S. Evans, Complex networks, Contemporary Physics, vol. 45, no. 6, pp. 455-474, 2004.
[9] S. Forman and B. K. Samanthula, “Secure Similar Document Detection: Optimized Computation Using the Jaccard Coefficient,” IEEE 4th International Conference on Big Data Security on Cloud (BigDataSecurity), pp. 1–4, 2018.
[10] C. A. Bliss, M. R. Frank, C. M. Danforth, and P. S. Dodds, “An evolutionary algorithm approach to link prediction in dynamic social networks,” Journal of Computational Science, vol. 5, no. 5, pp. 750–764, 2014.
[11] S. Fortunato, “Community detection in graphs,” Physics Reports. vol. 486, no. 3–5, pp. 75–174, 2010.
[12] J. Cheng, M. Leng, L. Li, H. Zhou, and X. Chen, “Active semi-supervised community detection based on must-link and cannot-link constraints,” PLoS ONE, vol. 9, no. 10. 2014.
[13] M. M. D. Khomami, A. Rezvanian, and M. R. Meybodi, “Distributed learning automata-based algorithm for community detection in complex networks,” International Journal of Modern Physics B, vol. 30, no. 8. 2016.
[14] M. Ghamgosar, M. M. D. Khomami, N. Bagherpour, and M. Reza, “An extended distributed learning automata based algorithm for solving the community detection problem in social networks,” Iran. Conf. Electr. Eng. ICEE 2017, pp. 1520–1526, 2017.
[15] M. M. D. Khomami, A. Rezvanian, and M. R. Meybodi, “A new cellular learning automata-based algorithm for community detection in complex social networks”, Journal of Computational Science. vol. 24, no.1, pp. 413–426, 2018.
[16] M. M. Daliri Khomami, A. Rezvanian, A. M. Saghiri, and M. R. Meybodi, “Utilizing Cellular Learning Automata for Finding Communities in Weighted Networks,” the 6th International Conference on Web Research, ICWR 2020. pp. 325–329, 2020.
[17] M. M. Daliri Khomami, A. Rezvanian, A. M. Saghiri, and M. R. Meybodi, “Overlapping Community Detection in Social Networks Using Cellular Learning Automata,” the 28th Iran. Conf. Electr. Eng. pp. 1–6, 2020.
[18] A. Fathinavid, “Multilayer cellular learning automata: A computational model to solve multilayer infrastructure problems with its application in community detection for multilayer networks”, Journal of Computational Science, vol. 61, p. 101683, 2022.
[19] S. A. H. Minoofam, A. Bastanfard, and M. R. Keyvanpour, "A transfer learning algorithm to improve the convergence rate and accuracy in cellular learning automata", Nashriyyah-i Muhandisi-i Barq va Muhandisi-i Kampyutar-i Iran, vol. 88, no. 2, p. 69, 2021.
[20] M. M. D, Khomami, A. Rezvanian, and M. R. Meybodi, “CFIN: A community-based algorithm for finding influential nodes in complex social networks”, Journal of Supercomput, vol. 77, pp. 2207–2236, 2021.
[21] J. A. Almendral, I. Leyva, D. Li, I. Sendiña-Nadal, S. Havlin, and S. Boccaletti, “Dynamics of overlapping structures in modular networks,” Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, vol. 82, no. 1. 2010.
[22] M. Hamann, U. Meyer, M. Penschuck, H. Tran, and D. Wagner, “I/O-efficient generation of massive graphs following the LFR benchmark,” ACM Journal of Experimental Algorithmics, vol.23, 2018.
[23] M. E. J. Newman, “Spectral methods for community detection and graph partitioning,” Phys. Rev. E - Stat. Nonlinear, Soft Matter Phys. vol. 88, no. 4, pp. 042822, 2013.
[24] F. Hu, J. Liu, L. Li, and J. Liang, “Community detection in complex networks using Node2vec with spectral clustering,” Phys. A Stat. Mech. its Appl. vol. 545, pp. 123633, 2020.
[25] B. He, L. Gu, and X. D. Zhang, “Nodal domain partition and the number of communities in networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2012, no. 2. 2012.
[26] P. Wu and L. Pan, “Multi-Objective Community Detection Based on Memetic Algorithm,”, PLoS ONE, vol.10, no.5 2015.
Journal of Soft Computing and Information Technology
Volume 12, Issue 3
December 2023
Pages 1-16

Files

Share

How to cite

Statistics