Improving the Precision of Link Prediction in Multi-Relational Heterogeneous Social Networks Using Evolutionary Algorithm (EA)

  • Yeganeh Sharifian -
Keywords: social networks, clustering, link prediction, evolutionary GA, AdaBoost algorithm


Fundamental changes have occurred in social interactions of the people with the advent and expansion of online social networks. With the expansion of social networks and the ever-increasing number of their users, the prediction of the users' relationships has turned into a difficult and complicated problem in these networks. Link prediction examines the links missing on the current network as well as the new links created in the future in social networks. Supervised and unsupervised methods can be used to predict the link. In unsupervised link-prediction method, the ranking of pair nodes is done only using one criterion, and in contrast to supervised link-prediction methods, they can complete the information from multiple scales and usually make real-world network model better. One of the methods proposed recently by Wang et al. states the problem of link prediction within the framework of supervised link prediction. This framework includes a re-weighing scheme based on the extracted features from high-profile interactions patterns across the network with great performance in link prediction, but in some supervised methods, it performs poorly not improving the precision of the link prediction. Thus, to solve the problem of link prediction, we introduce a new supervised link-prediction framework. Using the graph-edge clustering, supervised learning, and feature selection with EAs such as genetic algorithm (GA) in heterogeneous social networks, the link prediction problem was used. Furthermore, AdaBoost algorithm was applied to train learning models. In doing so, the DBLP scientific dataset was used. The results showed that feature selection using evolutionary GA improves the link prediction precision in social networks related to DBLP scientific publications by 5% in the logical regression model and 100% in the neural network and naive Bayes models. However, in the randomized forest model, precision is reduced by about 20%.


[1] X. Wang, and G. Sukthankar, “Link prediction in heterogeneous collaboration networks. ” 2013.
[2] W. Liu, and L. Lu, “Link prediction based on local random walk. ” 2010.
[3] H.R.d. Sa, and R.B.C. Prudˆencio, “Supervised link prediction in weighted networks, ”in Proceedings of International Joint Conference on Neural Networks, San Jose, California, USA. 2011.
[4] L. Backstrom, and J. Leskovec, “Supervised random walks: Predicting and recommending links in social networks.” 2011.
[5] M. Fire, and et al, “Links reconstruction attack using link prediction algorithms to compromise social networks privacy. ” 2012.
[6] J.B. Lee, and H. Adorna, “Link prediction in a modified heterogeneous bibliographic network,”in IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. 2012.
[7] H. Singh, D. Tomar, and S. Agarwal, “Link prediction for authorship association in heterogeneous network using streaming classification. ”International Journal of Grid and Distributed Computing. 2016.
[8] C. Chen, S. Deng, and J. Lu, “Link prediction in author collaboration network based on BP neural network. ” in a MATEC Web of Conferences. 2017.
[9] M. Meybodi, and et al., “A Link Prediction Method Based on Learning Automata in Social Networks. ” Journal of Computer & Robotics, 2018, p. 43-55.
[10] A.K.S. Kushwah, and A.K. Manjhvar, “A review on link prediction in social network. ”International Journal of Grid and Distributed Computing, 2016. 9.
[11] D.m. Boyd, N.B. Ellison, “Social network sites: definition, history, and scholarship. ” Journal of Computer-Mediated Communication, 2008.
[12] X. Wang, and G. Sukthankar, “Link prediction in multi-relational collaboration networks. ” in IEEE/ACM International Conference on Advances in Social Networks Analysis andMining. 2013.
[13] M.E.J. Newman, “Clustering and preferential attachment in growing networks0. ” PHYSICAL REVIEW E, 2001. 64.
[14] T. Zhou, and L. Lu, “Predicting missing links via local information. ”The European Physical Journal, 2009.
[15] S.R.A. Archana, and Dr.M.S.Thanabal, “Optimization algorithms for feature selection in classification: a survey.”International Journal of Innovative Research in Computer and Communication Engineering. (2016, Feb.). 4(2).
[16] J., Mirkovic, et al., “Genetic algorithms for intelligent internet search: A survey and a package for experimenting with various locality types, ” in IEEE TCCA Newsletter. 1999.
[17]R. Kumar, and D.R. Verma, “Classification algorithms for data mining: a survey.” International Journal of Innovations in Engineering and Technology (IJIET), (2012, Aug.). 1(2).