2692-4048ISSN (Online)
2770-0070ISSN (Print)
Volume 12 , Issue 2 , PP: 120-131, 2023 | Cite this article as | XML | Html | PDF | Full Length Article
Amr Al-Furas 1 * , Mohammed F. Alrahmawy 2 , Waleed Mohamed Al-Adrousy 3 , Samir Elmougy 4
Doi: https://doi.org/10.54216/FPA.120210
Complex networks are a diverse set of networks found in various fields, such as social, technological, and biological networks. One important task in complex network analysis is link prediction, which involves detecting missing links or predicting future link formation. Many methods based on network structure analysis have been developed for link prediction, including network representation learning (NRL) models that represent nodes in a low-dimensional space. Fusion-based attributed NRL methods are particularly effective, as they capture both content and structure information. However, NRL models for link prediction are binary classification models, which face challenges in identifying negative links and prioritizing predicted links. To address these challenges, we propose a novel approach that treats link prediction as a novelty detection problem. Our approach uses the Local Outlier Factor (LOF) algorithm to quantify the novelty of non-existent links based on the representations of existing links. Our experimental results show that our proposed approach outperforms existing methods, particularly when used with fusion-based attributed NRL models
Link Prediction , Network Representation Learning , Complex Network , Feature Fusion , LOF.
[1] Kumar, A., Singh, S.S., Singh, K., Biswas, B.J.P.A.S.M., Applications, i. Link prediction techniques, applications, and performance: A survey. 2020, 553, 124289.
[2] Daud, N.N., Ab Hamid, S.H., Saadoon, M., Sahran, F., Anuar, N.B.J.J.o.N., Applications, C. Applications of link prediction in social networks: A review. 2020, 166, 102716.
[3] Liben‐Nowell, D., Kleinberg, J.J.J.o.t.A.s.f.i.s., technology. The link‐prediction problem for social networks. 2007, 58, 1019-31.
[4] Aiello, L.M., Barrat, A., Schifanella, R., Cattuto, C., Markines, B., Menczer, F.J.A.T.o.t.W. Friendship prediction and homophily in social media. 2012, 6, 1-33.
[5] Wohlfarth, T., Ichise, R. Semantic and event-based approach for link prediction. In: International Conference on Practical Aspects of Knowledge Management, Springer, 2008, pp. 50-61.
[6] Chuan, P.M., Son, L.H., Ali, M., Khang, T.D., Huong, L.T., Dey, N.J.A.I. Link prediction in co-authorship networks based on hybrid content similarity metric. 2018, 48, 2470-86.
[7] Eirinaki, M., Gao, J., Varlamis, I., Tserpes, K.J.F.G.C.S. Recommender systems for large-scale social networks: A review of challenges and solutions. Elsevier, 2018, Vol. 78, pp. 413-8.
[8] Adamic, L.A., Adar, E.J.S.n. Friends and neighbors on the web. 2003, 25, 211-30.
[9] Zhou, T., Lü, L., Zhang, Y.-C.J.T.E.P.J.B. Predicting missing links via local information. 2009, 71, 623-30.
[10] Zeng, S.J.P.A.S.M., Applications, i. Link prediction based on local information considering preferential attachment. 2016, 443, 537-42.
[11] Muniz, C.P., Goldschmidt, R., Choren, R.J.K.-B.S. Combining contextual, temporal and topological information for unsupervised link prediction in social networks. 2018, 156, 129-37.
[12] Javari, A., Qiu, H., Barzegaran, E., Jalili, M., Chang, K.C.-C. Statistical link label modeling for sign prediction: Smoothing sparsity by joining local and global information. In: 2017 IEEE International Conference on Data Mining (ICDM), IEEE, 2017, pp. 1039-44.
[13] Das, S., Das, S.K. A probabilistic link prediction model in time-varying social networks. In: 2017 IEEE International Conference on Communications (ICC), IEEE, 2017, pp. 1-6.
[14] Bastami, E., Mahabadi, A., Taghizadeh, E.J.S., computation, e. A gravitation-based link prediction approach in social networks. 2019, 44, 176-86.
[15] Benchettara, N., Kanawati, R., Rouveirol, C. Supervised machine learning applied to link prediction in bipartite social networks. In: 2010 international conference on advances in social networks analysis and mining, IEEE, 2010, pp. 326-30.
[16] Wang, P., Xu, B., Wu, Y., Zhou, X.J.S.C.I.S. Link prediction in social networks: the state-of-the-art. 2015, 58, 1-38.
[17] Zhang, D., Yin, J., Zhu, X., Zhang, C. Network representation learning: A survey. IEEE transactions on Big Data. 2018, 6, 3-28.
[18] Makarov, I., Kiselev, D., Nikitinsky, N., Subelj, L., Elzeki, O.M., Shams, M., et al. Survey on graph embeddings and their applications to machine learning problems on graphs. PeerJ Computer Science. 2021.
[19] Donnat, C., Zitnik, M., Hallac, D., Leskovec, J. Learning structural node embeddings via diffusion wavelets. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 1320-9.
[20] Ribeiro, L.F., Saverese, P.H., Figueiredo, D.R. struc2vec: Learning node representations from structural identity. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, 2017, pp. 385-94.
[21] Hu, B., Wang, H., Yu, X., Yuan, W., He, T. Sparse network embedding for community detection and sign prediction in signed social networks. Journal of Ambient Intelligence and Humanized Computing. 2019, 10, 175-86.
[22] Sun, H., He, F., Huang, J., Sun, Y., Li, Y., Wang, C., et al. Network embedding for community detection in attributed networks. ACM Transactions on Knowledge Discovery from Data (TKDD). 2020, 14, 1-25.
[23] Wang, Z., Chen, C., Li, W. Predictive network representation learning for link prediction. In: Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval, 2017, pp. 969-72.
[24] Cai, L., Li, J., Wang, J., Ji, S.J.I.T.o.P.A., Intelligence, M. Line graph neural networks for link prediction. 2021.
[25] Li, G., Li, Q., Liu, J., Zhu, Y., Zhong, M. FANE: A Fusion-Based Attributed Network Embedding Framework. In: Web and Big Data: 5th International Joint Conference, APWeb-WAIM 2021, Guangzhou, China, August 23–25, 2021, Proceedings, Part I 5, Springer, 2021, pp. 53-60.
[26] Liu, T., Yin, J., Qin, Q.J.A.S. MFHE: Multi-View Fusion-Based Heterogeneous Information Network Embedding. 2022, 12, 8218.
[27] Yang, H., Chen, L., Pan, S., Wang, H., Zhang, P. Discrete embedding for attributed graphs. Pattern Recognition. 2022, 123, 108368.
[28] Al-Furas, A.T., Alrahmawy, M.F., Al-Adrousy, W.M., Elmougy, S.J.I.A. Deep Attributed Network Embedding via Weisfeiler-Lehman and Autoencoder. 2022, 10, 61342-53.
[29] Pan, Y., Zou, J., Qiu, J., Wang, S., Hu, G., Pan, Z. Joint network embedding of network structure and node attributes via deep autoencoder. Neurocomputing. 2022, 468, 198-210.
[30] Hong, R., He, Y., Wu, L., Ge, Y., Wu, X. Deep attributed network embedding by preserving structure and attribute information. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2019.
[31] Xia, F., Sun, K., Yu, S., Aziz, A., Wan, L., Pan, S., et al. Graph learning: A survey. IEEE Transactions on Artificial Intelligence. 2021, 2, 109-27.
[32] Zhou, J., Liu, L., Wei, W., Fan, J.J.A.C.S. Network representation learning: from preprocessing, feature extraction to node embedding. 2022, 55, 1-35.
[33] Zhang, M., Chen, Y.J.A.i.n.i.p.s. Link prediction based on graph neural networks. 2018, 31.
[34] Saxena, A., Fletcher, G., Pechenizkiy, M.J.E.D.S. NodeSim: node similarity based network embedding for diverse link prediction. 2022, 11, 24.
[35] Pio-Lopez, L., Valdeolivas, A., Tichit, L., Remy, É., Baudot, A.J.S.R. MultiVERSE: a multiplex and multiplex-heterogeneous network embedding approach. 2021, 11, 1-20.
[36] Zhang, H., Qiu, L., Yi, L., Song, Y. Scalable multiplex network embedding. In: IJCAI, 2018, Vol. 18, pp. 3082-8.
[37] Zhang, C., Shang, K.-K., Qiao, J.J.C. Adaptive similarity function with structural features of network embedding for missing link prediction. 2021, 2021.
[38] Breunig, M.M., Kriegel, H.-P., Ng, R.T., Sander, J. LOF: identifying density-based local outliers. In: Proceedings of the 2000 ACM SIGMOD international conference on Management of data, 2000, pp. 93-104.
[39] Grover, A., Leskovec, J. node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855-64.
[40] Rozemberczki, B., Kiss, O., Sarkar, R. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020, pp. 3125-32.
[41] Chen, J., Geyer, W., Dugan, C., Muller, M., Guy, I. Make new friends, but keep the old: recommending people on social networking sites. In: Proceedings of the SIGCHI conference on human factors in computing systems, 2009, pp. 201-10.
[42] Jaccard, P.J.B.S.V.S.N. Étude comparative de la distribution florale dans une portion des Alpes et des Jura. 1901, 37, 547-79.
[43] Barabâsi, A.-L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., Vicsek, T.J.P.A.S.m., et al. Evolution of the social network of scientific collaborations. 2002, 311, 590-614.
[44] Ou, M., Cui, P., Pei, J., Zhang, Z., Zhu, W. Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 1105-14.
[45] Yang, D., Rosso, P., Li, B., Cudre-Mauroux, P. Nodesketch: Highly-efficient graph embeddings via recursive sketching. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019, pp. 1162-72.
[46] Perozzi, B., Al-Rfou, R., Skiena, S. Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 701-10.
[47] Yang, C., Liu, Z., Zhao, D., Sun, M., Chang, E.Y. Network representation learning with rich text information. In: IJCAI, 2015, Vol. 2015, pp. 2111-7.
[48] Zhang, D., Yin, J., Zhu, X., Zhang, C. SINE: scalable incomplete network embedding. In: 2018 IEEE International Conference on Data Mining (ICDM), IEEE, 2018, pp. 737-46.
