Link Prediction in Social Networks Using the Extraction of Graph Topological Features

Amin Rezaeipanah¹ , Mousa Mojarad²

Section:Research Paper, Product Type: Journal
Vol.7 , Issue.5 , pp.1-7, Oct-2019

Online published on Oct 31, 2019

Copyright © Amin Rezaeipanah, Mousa Mojarad . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
The social relationships in social network analysis are considered using the terms node and link. The nodes are the individual actors in the networks and the links are the relationships between these actors. Regarding these links and their communications, the problem of link prediction is one of the most important challenges in social network analysis. Link prediction is one of the most popular applications in the online social network services helping users find new friends with similar interests. The present study tends to provide a hybrid criterion for comparing similarity among users with respect to the characteristics of the graph topology structure. The proposed method consists of two steps. In the first step, the similarity of users is calculated with different factors according to the similarities extracted from the features and the internetwork local circles. In the second step, the similarity of users is calculated using a hybrid similarity criterion. Different probabilistic factors have been used in the proposed similarity criterion, showing the effect of each feature on the final similarity criterion. The probability of any feature is optimized using a hill-climbing algorithm. The actual dataset from Twitter social network has been used in order to evaluate the performance of the proposed method. The results of the above tests indicate the higher performance of the proposed method compared with other similar methods

Key-Words / Index Term :
Social Networks, Link Prediction, Graph Topology, Similarity Criterion, Feature Extraction

References :
[1] B. Furht, “Handbook of social network technologies and applications,�. Springer Science & Business Media, 2010.
[2] L. Lü and T. Zhou, "Link prediction in complex networks: A survey," Physica A: statistical mechanics and its applications, vol. 390, no. 6, pp. 1150-1170, 2011.
[3] M. McPherson, L. Smith-Lovin, and J. M. Cook, "Birds of a feather: Homophily in social networks," Annual review of sociology, vol. 27, no. 1, pp. 415-444, 2001.
[4] V. Arnaboldi, M. G. Campana, F. Delmastro, and E. Pagani, "A personalized recommender system for pervasive social networks," Pervasive and Mobile Computing, vol. 36, pp. 3-24, 2017.
[5] M. A. Ahmad, Z. Borbora, J. Srivastava, and N. Contractor, "Link prediction across multiple social networks," International Conference on Data Mining Workshops (ICDMW), IEEE, pp. 911-918, 2010.
[6] D. Liben‐Nowell and J. Kleinberg, "The link‐prediction problem for social networks," journal of the Association for Information Science and Technology, vol. 58, no. 7, pp. 1019-1031, 2007.
[7] M. N. Hamid, M. A. Naser, M. K. Hasan, and H. Mahmud, "A cohesion-based friend-recommendation system," Social Network Analysis and Mining, vol. 4, no. 1, p. 176, 2014.
[8] T. L. Nguyen and T. H. Cao, "Multi-group-based User Perceptions for Friend Recommendation in Social Networks," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp. 525-534, 2014.
[9] P. Symeonidis and N. Mantas, "Spectral clustering for link prediction in social networks with positive and negative links," Social Network Analysis and Mining, vol. 3, no. 4, pp. 1433-1447, 2013.
[10] Y. Dhote, N. Mishra, and S. Sharma, "Survey and analysis of temporal link prediction in online social networks," in Advances in Computing, Communications and Informatics (ICACCI), 2013 International Conference on, IEEE, pp. 1178-1183, 2013.
[11] S. Yazdani, H. Nezamabadi-pour, and S. Kamyab, "A gravitational search algorithm for multimodal optimization," Swarm and Evolutionary Computation, vol. 14, pp. 1-14, 2014.
[12] J. Pei, X. Liu, P. M. Pardalos, W. Fan, S. Yang, and L. Wang, "Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain," The International Journal of Advanced Manufacturing Technology, vol. 70, no. 1-4, pp. 335-348, 2014.
[13] M. Doraghinejad, H. Nezamabadi-Pour, and A. Mahani, "Channel assignment in multi-radio wireless mesh networks using an improved gravitational search algorithm," Journal of Network and Computer Applications, vol. 38, pp. 163-171, 2014.
[14] F. Parvazeh, A. Harounabadi, and M. A. Naizari, "A recommender system for making friendship in social networks using graph theory and users profile," Journal of Current Research in Science, no. 1, p. 535, 2016.
[15] Z. Sun, L. Han, W. Huang, X. Wang, X. Zeng, M. Wang and H. Yan, "Recommender systems based on social networks," Journal of Systems and Software, vol. 99, pp. 109-119, 2015.
[16] M. Jalili, Y. Orouskhani, M. Asgari, N. Alipourfard, and M. Perc, "Link prediction in multiplex online social networks," Royal Society open science, vol. 4, no. 2, p. 160863, 2017.
[17] P. L. Szczepanski, A. S. Barcz, T. P. Michalak, and T. Rahwan, "The Game-Theoretic Interaction Index on Social Networks with Applications to Link Prediction and Community Detection," in IJCAI, vol. 15, pp. 638-644, 2015.
[18] J. Zhao, L. Miao, J. Yang, H. Fang, Q. M. Zhang, M. Nie and T. Zhou, "Prediction of links and weights in networks by reliable routes," Scientific reports, vol. 5, p. 12261, 2015.
[19] S. Han and Y. Xu, "Link Prediction in Microblog Network Using Supervised Learning with Multiple Features," JCP, vol. 11, no. 1, pp. 72-82, 2016.
[20] M. Ghalehgolabi, and A. Rezaeipanah, “Intrusion Detection System Using Genetic Algorithm and Data Mining Techniques Based on the Reduction,� International Journal of Computer Applications Technology and Research, vol. 6, no. 11, pp. 461-466, 2017.
[21] M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici, “Link prediction in social networks using computationally efficient topological features,� In 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing, pp. 73-80, 2011.
[22] Y. Dhote, N. Mishra, and S. Sharma, "Survey and analysis of temporal link prediction in online social networks," in Advances in Computing, International Conference on Communications and Informatics (ICACCI), IEEE, pp. 1178-1183, 2013.
[23] L. Katz, "A new status index derived from sociometric analysis," Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.
[24] A. Papadimitriou, P. Symeonidis, and Y. Manolopoulos, "Fast and accurate link prediction in social networking systems," Journal of Systems and Software, vol. 85, no. 9, pp. 2119-2132, 2012.
[25] T. Murata and S. Moriyasu, "Link prediction of social networks based on weighted proximity measures," in Proceedings of the IEEE/WIC/ACM international conference on web intelligence, IEEE Computer Society, pp. 85-88, 2007.
[26] M. Al Hasan and M. J. Zaki, "A survey of link prediction in social networks," in Social network data analytics, Springer, pp. 243-275, 2011.