Link prediction in fuzzy social networks using distributed learning automata

Springer Science and Business Media LLC - Tập 47 - Trang 837-849 - 2017
Behnaz Moradabadi1, Mohammad Reza Meybodi1
1Department of Computer Engineering, Amirkabir University of Technology, Tehran, Iran

Tóm tắt

Link prediction is an area of social network research that tries to predict future links using a social network structure. This paper proposes a novel link prediction method (FLP-DLA) that is based on fuzzy social networks and distributed learning automata (DLA). Distributed learning automata are reinforcement-based optimization tools which try to learn and converge to the optimal behavior from environmental feedback using graph navigation. In the preprocessing phase of the FLP-DLA, the proposed method tries to calculate a fuzzy strength for each link based on the information of the network, such as event time. In the main phase of the FLP-DLA, it uses these fuzzy strengths in addition to DLA to determine the strength of test links. In each iteration of the proposed method, the DLA tries to find a path between the endpoints of a random test link; following this, the FLP-DLA calculates the fuzzy strength of the obtained path using the fuzzy strengths of the links through the path, and rewards or penalizes the DLA based on the path strength. The main phase is repeated until the LAs converge to an action. Finally, we use the strength of the test links as the output of the link prediction. The results reported in this paper have proven satisfactory, indicating the usefulness of the proposed method for some social network datasets.

Tài liệu tham khảo

Lü L, Zhou T (2011) Link prediction in complex networks: A survey. Phys A: Stat Mech Its Appl 390(6):1150–1170 Al Hasan M, Zaki MJ (2011) A survey of link prediction in social networks Social network data analytics. Springer, pp 243– 275 Garcia G, Dario et al. (2014) Evaluating link prediction on large graphs. In: Artificial intelligence research and development: Proceedings of the 18th international conference of the Catalan association for artificial intelligence. IOS Press, vol 277 Armengol E (2015) Evaluating link prediction on large graphs. In: Artificial intelligence research and development: proceedings of the 18th international conference of the Catalan association for artificial intelligence. vol 277. IOS Press Huang Z, Li X, Chen H (2005) Link prediction approach to collaborative filtering. In: Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries. ACM Elmagarmid AK, Ipeirotis PG, Verykios VS (2007) Duplicate record detection: A survey. IEEE Trans Knowl Data Eng 19.1:1–16 Valerio F (2009) A graph-based semi-supervised algorithm for protein function prediction from interaction maps. In: International conference on learning and intelligent optimization. Springer Berlin Heidelberg, Heidelberg Liben-Nowell D, Kleinberg J (2007) The link-prediction problem for social networks. J Am Soc Inf Sci Technol 58.7:1019–1031 Narendra KS, Thathachar MAL (2012) Learning automata: an introduction. Courier Corporation Murata T, Moriyasu S (2008) Link prediction based on structural properties of online social networks. N Gener Comput 26(3):245–257 Al Hasan M, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning SDM’06: Workshop on link analysis, counter-terrorism and security Salton G, McGill MJ (1986) Introduction to modern information retrieval. McGraw-Hill, Inc., New York Albert-László B, Albert R (1999) Emergence of scaling in random networks. Science 286.5439:509–512 Newman MEJ (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64.2:025102 Adamic LA, Adar E (2003) Friends and neighbors on the web. Soc Netw 25.3:211–230 Rossetti G, Guidotti R, Pennacchioli D, Pedreschi D, Giannotti F (2015) Interaction Prediction in dynamic networks exploiting community discovery. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks ana. s and mining, 2015, pp 553–558 : s.n Bliss CA, Frank MR, Danforth CM, Dodds PS (2014) An evolutionary algorithm approach to link prediction in dynamic social networks. J Comput Sci 5(5):750–764 Fei T, Xia Y, Zhu B (2014) Link prediction in complex networks: a mutual information perspective. PloS One 9.9:e107056 Ozcan A, Oguducu SG (2015) Multivariate temporal Link Prediction in evolving social networks. In: 2015 IEEE/ACIS 14th international conference on computer and information science (ICIS), pp 185–190 Huang S, Tang Y, Tang F, Li J (2014) ink prediction based on time-varied weight in co-authorship network. In: Proceedings of the 2014 IEEE 18th international conference on computer supported cooperative work in design (CSCWD), pp 706–709 Moradabadi B, Meybodi MR (2016) Link prediction based on temporal similarity metrics using continuous action set learning automata. Phys A: Stat Mech Its Appl 460:361–373 Zadeh LA (1965) Fuzzy sets. Inf Control 8(3):338–353 Nair PS, Sarasamma ST (2007) Data mining through fuzzy social network analysis Fuzzy information processing society, 2007. NAFIPS’07. Annual Meeting of the North American, pp 251–255 Brunelli M, Fedrizzi M (2009) A fuzzy approach to social network analysis International conference on advances in social network analysis and mining 2009. ASONAM’09, pp 225– 230 Bastani S, Jafarabad AK, Zarandi MHF (2013) Fuzzy models for link prediction in social networks. Int J Intell Syst 28(8):768–786 Yang L, Zhang W, Chen Y (2015) Time-series prediction based on global fuzzy measure in social networks. Frontiers, 1 He Y, Liu JNK, Hu Y, Wang X (2015) OWA operator based link prediction ensemble for social network. Expert Syst Appl 42(1):21–50 Thathachar MAL, Sastry PS (2003) Networks of learning automata: Techniques for online stochastic optimization. Springer Rezvanian A, Meybodi MR (2010) An adaptive mutation operator for artificial immune network using learning automata in dynamic environments 2010 2nd world congress on nature and biologically inspired computing (NaBIC), pp 479–483 Rezvanian A, Meybodi MR (2010) LACAIS: learning automata based cooperative artificial immune system for function optimization. In: Contemporary computing. Springer, pp 64–75 Rezvanian A, Rahmati M, Meybodi MR (2014) Sampling from complex networks using distributed learning automata. Phys A: Stat Mech Its Appl 396:224–234 Beigy H, Meybodi MR (2006) Utilizing distributed learning automata to solve stochastic shortest path problems. Int J Uncertainty Fuzziness Knowledge Based Syst 14(5):591–615 Soleimani-Pouri M, Rezvanian A, Meybodi MR (2012) Solving maximum clique problem in stochastic graphs using learning automata. In: 2012 4th international conference on computational aspects of social networks (CASoN), pp 115–119 Hu R-J, Li Q, Zhang G-Y, Ma W-C (2015) Centrality measures in directed fuzzy social networks. Fuzzy Info Eng 7(1):115–128 Lü L, Zhou T (2011) Link prediction in complex networks: A survey. Phys A: Stat Mech Its Appl 390.6:1150–1170 Rossetti G, Guidotti R, Pennacchioli D, Pedreschi D, Giannotti F (2015) Interaction prediction in dynamic networks exploiting community discovery. In: Proceedings of the 2015 IEEE/ACM international conference on advances in social networks analysis and mining, 2015, pp 553–558 : s.n Bliss CA, Frank MR, Danforth CM, Dodds PS (2014) An evolutionary algorithm approach to link prediction in dynamic social networks. J Comput Sci 5(5):750–764