A New Multi-Wave Cellular Learning Automata and Its Application for Link Prediction Problem in Social Networks

Subject Areas : Journal of Computer & Robotics

Mozhdeh Khaksar Manshad ¹ , Mohammad Reza Meybodi ² , Afshin Salajegheh ³

1 - Department of Computer Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
2 - Amirkabir University of Technology, Tehran, Iran
3 - Department of Computer Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

Received: 2021-06-05 Accepted : 2021-07-01 Published : 2021-06-01

Keywords: Cellular Learning Automata, Social networks, Link Prediction problem,

Abstract :

Link Prediction (LP) is one of the main research areas in Social Network Analysis (SNA). The problem of LP can help us understand the evolution mechanism of social networks, and it can be used in different applications such as recommendation systems, bioinformatics, and marketing. Social networks can be shown as a graph, and LP algorithms predict future connections by using previous network information. In this paper, a multi-wave cellular learning automaton (MWCLA) is introduced and used to solve the LP problem in social networks. The proposed model is a new CLA with a connected structure and a module of LAs in each cell where a cell module’s neighbors are its successors. In the MWCLA method for improving convergence speed and accuracy, multiple waves have been used parallelly in the network. By using multiple waves, different information of the network can be considered for predicting links in the social network. Here we show that the model converges upon a stable and compatible configuration. Then for the LP problem, it has been demonstrated that MWCLA produces much better results than other approaches compared to some state-of-the-art methods.

References:

[1] Daud NN, Ab Hamid SH, Saadoon M, Sahran F, Anuar NB (2020) Applications of link prediction in social networks: A review. Journal of Network and Computer Applications:102716

[2] Mofrad MH, Sadeghi S, Rezvanian A, Meybodi MR (2015) Cellular edge detection: Combining cellular automata and cellular learning automata. AEU-International Journal of Electronics and Communications 69 (9):1282-1290

[3] Rezvanian A, Saghiri AM, Vahidipour SM, Esnaashari M, Meybodi MR (2018) Recent advances in learning automata, vol 754 %@ 3319724282. Springer,

[4] Rezvanian A, Saghiri AM, Vahidipour SM, Esnaashari M, Meybodi MR (2018) Cellular learning automata. In:  Recent Advances in Learning Automata. Springer, pp 21-88

[5] Ghavipour M, Meybodi MR (2017) Irregular cellular learning automata-based algorithm for sampling social networks. Engineering Applications of Artificial Intelligence 59:244-259 %@ 0952-1976 Zhao Y, Jiang W, Li S, Ma Y, Su G, Lin X (2015) A cellular learning automata based algorithm for detecting community structure in complex networks. Neurocomputing 151:1216-1226 %@ 0925-2312

[6] Manshad MK, Manshad AK, Meybodi MR Memory/search RCLA-EC: A CLA-EC for moving parabola problem. In, 2012. IEEE, pp 732-737 %@ 8988678559

[7] Manshad MK, Meybodi MR, Salajegheh A A new irregular cellular learning automata-based evolutionary computation for time series link prediction in social networks.  Mirsaleh MR, Meybodi MR (2016) A Michigan memetic algorithm for solving the community detection problem in complex network. Neurocomputing 214:535-545 %@ 0925-2312

[8] Vafashoar R, Meybodi MR, Azandaryani AHM (2012) CLA-DE: a hybrid model based on cellular learning automata for numerical optimization. Applied Intelligence 36 (3):735-748 %@ 0924-0669X

[9] Patel DK, More SA Edge detection technique by fuzzy logic and Cellular Learning Automata using fuzzy image processing. In, 2013. IEEE, pp 1-6 %@ 146732907X

[10] Moradabadi B, Meybodi MR (2018) Wavefront cellular learning automata. Chaos: An Interdisciplinary Journal of Nonlinear Science 28 (2):021101 %@ 021054-021500

[11] Manshad MK, Meybodi MR, Salajegheh A (2021) A new irregular cellular learning automata-based evolutionary computation for time series link prediction in social networks. Applied Intelligence 51 (1):71-84

[12] Akcora CG, Carminati B, Ferrari E (2013) User similarities on social networks. Social Network Analysis and Mining 3 (3):475-495 %@ 1869-5450

[13] Valverde-Rebaza J, de Andrade Lopes A (2013) Exploiting behaviors of communities of twitter users for link prediction. Social Network Analysis and Mining 3 (4):1063-1074 %@ 1869-5450

[14] Liu H, Hu Z, Haddadi H, Tian H (2013) Hidden link prediction based on node centrality and weak ties. EPL (Europhysics Letters) 101 (1):18004 %@ 10295-15075

[15] Menon AK, Elkan C Link prediction via matrix factorization. In, 2011. Springer, pp 437-452

[16] Bliss CA, Frank MR, Danforth CM, Dodds PS (2014) An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science 5 (5):750-764 %@ 1877-7503

[17] Rossetti G, Guidotti R, Pennacchioli D, Pedreschi D, Giannotti F Interaction prediction in dynamic networks exploiting community discovery. In, 2015. IEEE, pp 553-558 %@ 1450338542

[18] Moradabadi B, Meybodi MR (2017) A novel time series link prediction method: Learning automata approach. Physica A: Statistical Mechanics and its Applications 482:422-432

[19] Moradabadi B, Meybodi MR (2016) Link prediction based on temporal similarity metrics using continuous action set learning automata. Physica a: statistical mechanics and its applications 460:361-373

[20] Moradabadi B, Meybodi MR (2017) Link prediction in fuzzy social networks using distributed learning automata. Applied Intelligence 47 (3):837-849 %@ 0924-0669X

[21] Bliss CA, Frank MR, Danforth CM, Dodds PS (2014) An evolutionary algorithm approach to link prediction in dynamic social networks. Journal of Computational Science 5 (5):750-764

[22] Sherkat E, Rahgozar M, Asadpour M (2015) Structural link prediction based on ant colony approach in social networks. Physica A: Statistical Mechanics and its Applications 419:80-94 %@ 0378-4371

[23] Tan F, Xia Y, Zhu B (2014) Link prediction in complex networks: a mutual information perspective. PloS one 9 (9):e107056

Esnaashari M, Meybodi MR (2014) Irregular cellular learning automata. IEEE Transactions on Cybernetics 45 (8):1622-1632 %@ 2168-2267

[24] Saghiri AM, Meybodi MR (2017) A closed asynchronous dynamic model of cellular learning automata and its application to peer-to-peer networks. Genetic Programming and Evolvable Machines 18 (3):313-349 %@ 1389-2576

[25] Thathachar MAL, Arvind MT (1998) Parallel algorithms for modules of learning automata. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 28 (1):24-33 %@ 1083-4419

[26] Manshad MK, Meybodi MR, Salajegheh A A variable action set cellular learning automata-based algorithm for link prediction in online social networks. The Journal of Supercomputing:1-29