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

Authors

1 Department of Computer Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran

2 Amirkabir University of Technology, Tehran, Iran

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.

Keywords


  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
  24. Esnaashari M, Meybodi MR (2014) Irregular cellular learning automata. IEEE Transactions on Cybernetics 45 (8):1622-1632 %@ 2168-2267
  25. 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
  26. 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
  27. 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
Volume 14, Issue 1
Winter and Spring 2021
Pages 1-21
  • Receive Date: 05 June 2021
  • Revise Date: 27 June 2021
  • Accept Date: 01 July 2021