New Criteria for Predicting Links based on Node Composition and Network Structure

Document Type : Persian Original Article

Authors

1 Department of Computer Engineering, Shiraz Branch, Islamic Azad University, Shiraz, Iran

2 department of computer engineering, Shiraz branch, Islamic Azad university, Shiraz, Iran

Abstract

Abstract - Currently, the study of social space and social networks and the analysis of these networks has grown significantly. In real life, people are not independent of each other. People in social groups are interdependent. One of the most widely used fields in the study of social networks is the issue of link identification, which has recently become popular among domestic and foreign researchers. Link prediction can be used not only in the field of social networking, but also in areas such as bioinformatics, to explore the interrelationships between proteins, in the field of e-commerce. The main purpose in the field of link identification is to investigate the possibility of creating or deleting links between members in the future state of the network using the analysis of its current state. In this study, using local criteria of neighbor-based similarity and general path-based similarity criteria, both of which use the graph structure, new similarity criteria have been introduced. The results of the work have been tested based on precision and AUC criteria on the data set and show the superiority of the proposed method that uses a combination of graph structure information like path, neighbor and node degrees over the criteria that use only the path or the neighbor.

Keywords

References

[1] Borgatti, S. P., Everett, M. G., & Johnson, J. C. (2018). Analyzing social networks. Sage.
[2] Wasserman, Stanley; Faust, Katherine (1994). "Social Network Analysis in the Social and Behavioral Sciences". Social Network Analysis: Methods and Applications. Cambridge University Press. pp. 127. ISBN 9780521387071.
[3] Liben‐Nowell, D., & Kleinberg, J. (2007). The link‐prediction problem for social networks. Journal of the American society for information science and technology, 58(7), 1019-1031.
[4] Aiello L M, Barrat A, Schifanella R, et al. Friendship prediction and homophily in social media. ACM Trans Web, 2012, 6: 9
[5] Mori J, Kajikawa Y, Kashima H, et al. Machine learning approach for finding business partners and building reciprocal relationships. Expert Syst Appl, 2012, 39: 10402–10407
[6] Wohlfarth T, Ichise R. Semantic and event-based approach for link prediction. In: Proceedings of the 7th International Conference on Practical Aspects of Knowledge Management (PAKM’08), Yokohama, 2008. 50–61
[7] Raeder T, Lizardo O, Hachen D, et al. Predictors of short-term decay of cell phone contacts in a large scale communication network. Soc Netw, 2011, 33: 245–257
[8] Marchette D J, Priebe C E. Predicting unobserved links in incompletely observed networks. Comput Stat Data Anal, 2008, 52: 1373–1386
[9] Kim M, Leskovec J. The network completion problem: inferring missing nodes and edges in networks. In: Proceedings of the 11th SIAM International Conference on Data Mining (SDM’11), Mesa, 2011. 47–58
[10] Barab´asi A L, Jeong H, N´eda Z, et al. Evolution of the social network of scientific collaborations. Physica A, 2002, 311: 590–614
[11] Almansoori W, Gao S, Jarada T N, et al. Link prediction and classification in social networks and its application in healthcare and systems biology. Netw Model Anal Health Inform Bioinform, 2012, 1: 27–36
[12] Wang, P., Xu, B., Wu, Y., & Zhou, X. (2015). Link prediction in social networks: the state-of-the-art. Science China Information Sciences, 58(1), 1-38.
[13] Adamic L A, Adar E. Friend and neighbors on the web. Soc Networks, 2003, 25: 211–230
[14] Katz L. A new status index derived from sociometric analysis. Psychometrika, 1953, 18: 39–43
[15] Rafiee, Samira, Chiman Salavati, and Alireza Abdollahpouri. "CNDP: Link prediction based on common neighbors degree penalization." Physica A: Statistical Mechanics and its Applications 539 (2020): 122950.
[16] V. Martínez, F. Berzal, J.-C. Cubero, Adaptive degree penalization for link prediction, J. Comput. Sci. 13 (2016) 1–9.
[17] F. Li, J. He, G. Huang, Y. Zhang, Y. Shi, R. Zhou, Node-coupling clustering approaches for link prediction, Knowl.-Based Syst. 89 (2015) 669–680.
[18] F. Aghabozorgi, M.R. Khayyambashi, A new similarity measure for link prediction based on local structures in social networks, Physica A 501 (2018) 12–23.
[19] Yu, Chuanming, et al. "Similarity-based link prediction in social networks: A path and node combined approach." Journal of Information Science 43.5 (2017): 683-695.
[20] Yin Z, Gupta M, Weninger T and Han J. LINKREC: A unified framework for link recommendation with user attributes and graph structure. In: Proceedings of the 19th International Conference on World Wide Web. North Carolina, USA: ACM, 2010, pp. 1211–1212.
[21] Wang D, Pedreschi D, Song C, Giannotti F and Barabasi AL. Human mobility, social ties, and link prediction. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11. New York: ACM, 2011, pp. 1100–1108.
[22] Z. Liu, Q.M. Zhang, L. L, T. Zhou, Link prediction in complex networks: a local naive bayes model, EPL Europhys. Lett. (2011) 96.
[23] J. Feng, J. Zhao, K. Xu, Link prediction in complex networks: a clustering perspective, Eur. Phys. J. B 85 (2012) 1–9.
[24] Bastami, E., Mahabadi, A., & Taghizadeh, E. (2019). A gravitation-based link prediction approach in social networks. Swarm and evolutionary computation, 44, 176-186.
 [25] Newman M E J. Clustering and preferential attachment in growing networks. Phys Rev E, 2001, 64: 025102
[26] Zhou, M., Li, B., Yang, M. & Pan, L. TeleGraph: A Benchmark Dataset for Hierarchical Link Prediction. arXiv preprint arXiv:2204.07703 (2022).
[27] Long, Y. et al. Pre-training graph neural networks for link prediction in biomedical networks. Bioinformatics 38, 2254–2262 (2022).
[28] Kumar, S., Mallik, A. & Panda, B. S. Link prediction in complex networks using node centrality and light gradient boosting machine. World Wide Web 1–27 (2022).
Journal of Soft Computing and Information Technology
Volume 11, Issue 2 - Serial Number 36
Summer
September 2022
Pages 41-52

Files

Share

How to cite

Statistics