(Center for Artificial Intelligence Technology, Universiti Kebangsaan Malaysia &
Department of Informatics, Universitas Ahmad Dahlan, Indonesia, Indonesia)(2) Zulaiha Ali Othman
(Center for Artificial Intelligence Technology, Universiti Kebangsaan Malaysia, Malaysia)(3) Azuraliza Abu Bakar
(Center for Artificial Intelligence Technology, Universiti Kebangsaan Malaysia, Malaysia)*corresponding author
AbstractThe cold-start problem is a condition for a new node to join a network with no available information or an isolated node. Most studies use topological network information with the Triadic Closure principles to predict links in future networks. However, the method based on the Triadic Closure principles cannot predict the future link due to no common neighbors between the predicted node pairs. Adamic Adar is one of the methods based on the Triadic Closure principles. This paper proposes three methods for extending Adamic Adar based on network metrics. The main objective is to utilize the network metrics to attract the isolated node or new node to make new relationships in the future network. The proposed method is called the extended Adamic Adar index based on Degree Centrality (DCAA), Closeness Centrality (CloCAA), and Clustering Coefficient (CluCAA). Experiments were conducted by sampling 10% of the dataset as testing data. The proposed method is examined using the four real-world networks by comparing the AUC score. Finally, the experiment results show that the DCAA and CloCAA can predict up to 99% of node pairs with a cold-start problem. DCAA and CloCAA outperform the benchmark, with an AUC score of up to 0,960. This finding shows that the extended Adamic Adar index can overcome prediction failures on node pairs with cold-start problems. In addition, prediction performance is also improved compared to the original Adamic Adar. The experiment results are promising for future research due to successfully improving the prediction performance and overcoming the cold-start problem.
KeywordsLink Prediction; Triadic Closure;Network Metrics;Degree Centrality;Closeness Centrality;Clustering Centrality
|
DOIhttps://doi.org/10.26555/ijain.v8i3.882 |
Article metricsAbstract views : 772 | PDF views : 324 |
Cite |
Full Text Download
|
References
[1] F. Tahmasebi, M. Meghdadi, S. Ahmadian, and K. Valiallahi, “A hybrid recommendation system based on profile expansion technique to alleviate cold start problem,” Multimed. Tools Appl., vol. 80, no. 2, pp. 2339–2354, Jan. 2021, doi: 10.1007/s11042-020-09768-8.
[2] S. Natarajan, S. Vairavasundaram, S. Natarajan, and A. H. Gandomi, “Resolving data sparsity and cold start problem in collaborative filtering recommender system using Linked Open Data,” Expert Syst. Appl., vol. 149, p. 113248, Jul. 2020, doi: 10.1016/j.eswa.2020.113248.
[3] Y. Zhu et al., “Addressing the Item Cold-Start Problem by Attribute-Driven Active Learning,” IEEE Trans. Knowl. Data Eng., vol. 32, no. 4, pp. 631–644, Apr. 2020, doi: 10.1109/TKDE.2019.2891530.
[4] J. Misztal-Radecka, B. Indurkhya, and A. Smywiński-Pohl, “Meta-User2Vec model for addressing the user and item cold-start problem in recommender systems,” User Model. User-adapt. Interact., vol. 31, no. 2, pp. 261–286, Apr. 2021, doi: 10.1007/s11257-020-09282-4.
[5] D. Cai, S. Qian, Q. Fang, J. Hu, and C. Xu, “User Cold-start Recommendation via Inductive Heterogeneous Graph Neural Network,” ACM Trans. Inf. Syst., Sep. 2022, doi: 10.1145/3560487.
[6] K. Pliakos, S.-H. Joo, J. Y. Park, F. Cornillie, C. Vens, and W. Van den Noortgate, “Integrating machine learning into item response theory for addressing the cold start problem in adaptive learning systems,” Comput. Educ., vol. 137, pp. 91–103, Aug. 2019, doi: 10.1016/j.compedu.2019.04.009.
[7] M. Vahidi Farashah, A. Etebarian, R. Azmi, and R. Ebrahimzadeh Dastjerdi, “A hybrid recommender system based-on link prediction for movie baskets analysis,” J. Big Data, vol. 8, no. 1, p. 32, Dec. 2021, doi: 10.1186/s40537-021-00422-0.
[8] J. Feng, Z. Xia, X. Feng, and J. Peng, “RBPR: A hybrid model for the new user cold start problem in recommender systems,” Knowledge-Based Syst., vol. 214, p. 106732, Feb. 2021, doi: 10.1016/j.knosys.2020.106732.
[9] J. Moon, J. Kim, P. Kang, and E. Hwang, “Solving the Cold-Start Problem in Short-Term Load Forecasting Using Tree-Based Methods,” Energies, vol. 13, no. 4, p. 886, Feb. 2020, doi: 10.3390/en13040886.
[10] Z. Li et al., “HML4Rec: Hierarchical meta-learning for cold-start recommendation in flash sale e-commerce,” Knowledge-Based Syst., vol. 255, p. 109674, Nov. 2022, doi: 10.1016/j.knosys.2022.109674.
[11] M. Tang and W. Wang, “Cold-start Link Prediction Integrating Community Information via Multi-Nonnegative Matrix Factorization,” Chaos, Solitons & Fractals, vol. 162, p. 112421, Sep. 2022, doi: 10.1016/j.chaos.2022.112421.
[12] M. Tang, W. Yu, X. Li, X. Chen, W. Wang, and Z. Liu, “Cold-start Link Prediction via Weighted Symmetric Nonnegative Matrix Factorization with Graph Regularization,” Comput. Syst. Sci. Eng., vol. 43, no. 3, pp. 1069–1084, 2022, doi: 10.32604/csse.2022.028841.
[13] S. Wu, Q. Zhang, C. Xue, and X. Liao, “Cold-start Link Prediction in Multi-relational Networks based on Network Dependence Analysis,” Phys. A Stat. Mech. its Appl., vol. 515, pp. 558–565, 2019, doi: 10.1016/j.physa.2018.09.082.
[14] H. Yuliansyah, Z. A. Othman, and A. A. Bakar, “Taxonomy of link prediction for social network analysis: a review,” IEEE Access, vol. 8, pp. 183470–183487, 2020, doi: 10.1109/ACCESS.2020.3029122.
[15] K. Li, L. Tu, and L. Chai, “Ensemble-model-based Link Prediction of Complex Networks,” Comput. Networks, vol. 166, p. 106978, 2020, doi: 10.1016/j.comnet.2019.106978.
[16] J. Liu et al., “Collaborative linear manifold learning for link prediction in heterogeneous networks,” Inf. Sci. (Ny)., vol. 511, pp. 297–308, Feb. 2020, doi: 10.1016/j.ins.2019.09.054.
[17] G. Chen, C. Xu, J. Wang, J. Feng, and J. Feng, “Graph Regularization Weighted Nonnegative Matrix Factorization for Link Prediction in Weighted Complex Network,” Neurocomputing, vol. 369, pp. 50–60, 2019, doi: 10.1016/j.neucom.2019.08.068.
[18] V. Leroy, B. B. Cambazoglu, and F. Bonchi, “Cold start link prediction,” in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010, pp. 393–402. doi: 10.1145/1835804.1835855.
[19] P. Wang, B. W. Xu, Y. R. Wu, and X. Y. Zhou, “Link prediction in social networks: the state-of-the-art,” Sci. China Inf. Sci., vol. 58, no. 1, pp. 1–38, 2015, doi: 10.1007/s11432-014-5237-y.
[20] S. Haghani and M. R. Keyvanpour, “A Systemic Analysis of Link Prediction in Social Network,” Artif. Intell. Rev., vol. 52, no. 3, pp. 1–35, 2017, doi: 10.1007/s10462-017-9590-2.
[21] H. Huang, Y. Dong, J. Tang, H. Yang, N. V. Chawla, and X. Fu, “Will Triadic Closure Strengthen Ties in Social Networks?,” ACM Trans. Knowl. Discov. Data, vol. 12, no. 3, pp. 1–25, Jun. 2018, doi: 10.1145/3154399.
[22] A. Asikainen, G. Iñiguez, J. Ureña-Carrión, K. Kaski, and M. Kivelä, “Cumulative effects of triadic closure and homophily in social networks,” Sci. Adv., vol. 6, no. 19, May 2020, doi: 10.1126/sciadv.aax7310.
[23] A. Aleta, M. Tuninetti, D. Paolotti, Y. Moreno, and M. Starnini, “Link prediction in multiplex networks via triadic closure,” Phys. Rev. Res., vol. 2, no. 4, p. 042029, Nov. 2020, doi: 10.1103/PhysRevResearch.2.042029.
[24] L. Ge and A. Zhang, “Pseudo Cold Start Link Prediction with Multiple Sources in Social Networks,” in Proceedings of the 12th SIAM International Conference on Data Mining, SDM 2012, 2012, pp. 768–779. doi: 10.1137/1.9781611972825.66.
[25] M. Yan, J. Sang, T. Mei, and C. Xu, “Friend Transfer: Cold-start Friend Recommendation with Cross-platform Transfer Learning of Social Knowledge,” in 2013 IEEE International Conference on Multimedia and Expo (ICME), 2013, pp. 1–6, doi: 10.1109/ICME.2013.6607510
[26] J. Zhang, X. Kong, and P. S. Yu, “Predicting Social Links for New Users Across Aligned Heterogeneous Social Networks,” in 2013 IEEE 13th International Conference on Data Mining, 2013, pp. 1289–1294. doi: 10.1109/ICDM.2013.134.
[27] V. A. Rohani, Z. M. Kasirun, S. Kumar, and S. Shamshirband, “An Affective Recommender Algorithm for Cold-start Problem in Academic Social Networks,” Math. Probl. Eng., vol. 2014, 2014, doi: 10.1155/2014/123726.
[28] X. Han, L. Wang, S. N. Han, C. Chen, N. Crespi, and R. Farahbakhsh, “Link Prediction for New Users in Social Networks,” in 2015 IEEE International Conference on Communications (ICC), 2015, pp. 1250–1255. doi: 10.1109/ICC.2015.7248494.
[29] Z. Wang, J. Liang, R. Li, and Y. Qian, “An Approach to Cold-start Link Prediction: Establishing Connections between Non-topological and Topological Information,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 11, pp. 2857–2870, 2016, doi: 10.1109/TKDE.2016.2597823.
[30] J. Zhu et al., “CHRS: Cold Start Recommendation Across Multiple Heterogeneous Information Networks,” IEEE Access, vol. 5, no. 8, pp. 15283–15299, 2017, doi: 10.1109/ACCESS.2017.2726339.
[31] S. Wu, Q. Zhang, and M. Wu, “Cold-start Link Prediction in Multi-relational Networks,” Phys. Lett. A, vol. 381, no. 39, pp. 3405–3408, 2017, doi: 10.1016/j.physleta.2017.08.046.
[32] L. Xu, X. Wei, J. Cao, and P. S. Yu, “On Learning Community-specific Similarity Metrics for Cold-start Link Prediction,” in 2018 International Joint Conference on Neural Networks (IJCNN), Jul. 2018, pp. 1–8. doi: 10.1109/IJCNN.2018.8489683.
[33] L. Xu, X. Wei, J. Cao, and P. S. Yu, “On Learning Mixed Community-Specific Similarity Metrics for Cold-start Link Prediction,” in Proceedings of the 26th International Conference on World Wide Web Companion - WWW ’17 Companion, 2017, pp. 861–862. doi: 10.1145/3041021.3054269.
[34] H. Nassar, A. R. Benson, and D. F. Gleich, “Neighborhood and PageRank methods for pairwise link prediction,” Soc. Netw. Anal. Min., vol. 10, no. 1, p. 63, Dec. 2020, doi: 10.1007/s13278-020-00671-6.
[35] S. Liu, X. Ji, C. Liu, and Y. Bai, “Similarity indices based on link weight assignment for link prediction of unweighted complex networks,” Int. J. Mod. Phys. B, vol. 31, no. 02, p. 1650254, Jan. 2017, doi: 10.1142/S0217979216502544.
[36] M. Z. Al-Taie and S. Kadry, Python for Graph and Network Analysis. Cham: Springer International Publishing, 2017. doi: 10.1007/978-3-319-53004-8.
[37] L. A. Adamic and E. Adar, “Friends and Neighbors on the Web,” Soc. Networks, vol. 25, no. 3, pp. 211–230, Jul. 2003, doi: 10.1016/S0378-8733(03)00009-1.
[38] D. Liben-Nowell and J. Kleinberg, “The Link-Prediction Problem for Social Networks,” J. Am. Soc. Inf. Sci. Technol., vol. 58, no. 7, pp. 1019–1031, 2007, doi: 10.1002/asi.
[39] F. Pedregosa et al., “Scikit-learn: Machine Learning in {P}ython,” J. Mach. Learn. Res., vol. 12, pp. 2825–2830, 2011, available at: Google Scholar.
[40] M. E. J. Newman, “Clustering and Preferential Attachment in Growing Networks,” Phys. Rev. E, vol. 64, no. 2, p. 025102, Jul. 2001, doi: 10.1103/PhysRevE.64.025102.
[41] T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting Missing Links via Local Information,” Eur. Phys. J. B, vol. 71, no. 4, pp. 623–630, Oct. 2009, doi: 10.1140/epjb/e2009-00335-8.
[42] P. Jaccard, “Étude comparative de la distribution florale dans une portion des Alpes et des Jura,” Bull Soc Vaudoise Sci Nat, vol. 37, pp. 547–579, 1901, doi: 10.5169/SEALS-266450
[43] G. Salton and M. J. McGill, Introduction to Modern Information Retrieval. McGraw-Hill, pp. 528 , 1983, available at: Google Scholar
[44] T. J. Sørensen, “A method of establishing groups of equal amplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons,” I kommission hos E. Munksgaard, vol. 5, pp. 34, 1948, available at: Books Google
[45] E. A. Leicht, P. Holme, and M. E. J. Newman, “Vertex Similarity in Networks,” Phys. Rev. E, vol. 73, no. 2, p. 026120, Feb. 2006, doi: 10.1103/PhysRevE.73.026120.
[46] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, “Hierarchical Organization of Modularity in Metabolic Networks,” Science (80-. )., vol. 297, no. 5586, pp. 1551–1555, Aug. 2002, doi: 10.1126/science.1073374.
[47] L. L. Linyuan and T. Zhou, “Link prediction in complex networks: A survey,” Phys. A Stat. Mech. its Appl., vol. 390, no. 6, pp. 1150–1170, 2011, doi: 10.1016/j.physa.2010.11.027.
[48] J. Leskovec and A. Krevl, “SNAP Datasets: Stanford Large Network Dataset Collection.” Jun. 2014. Available at: https://snap.stanford.edu/data/
[49] R. A. Rossi and N. K. Ahmed, “The network data repository with interactive graph analytics and visualization,” 2015. [Online]. Available: http://networkrepository.com
[50] J. Kunegis, “Konect: the koblenz network collection,” in International Conferenceon World Wide Web, 2014, pp. 1343–1350, doi: 10.1145/2487788.2488173
[51] D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, vol. 393, pp. 440–442, Jun. 1998, doi: 10.1038/30918.
[52] J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Signed Networks in Social Media,” in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, 2010, pp. 1361–1370, doi: 10.1145/1753326.1753532
[53] J. Moody, “Peer influence groups: identifying dense clusters in large networks,” Soc. Networks, vol. 23, no. 4, pp. 261–283, Oct. 2001, doi: 10.1016/S0378-8733(01)00042-9.
[54] B. Pandey, P. K. Bhanodia, A. Khamparia, and D. K. Pandey, “A Comprehensive Survey of Edge Prediction in Social Networks: Techniques, Parameters and Challenges,” Expert Syst. Appl., vol. 124, pp. 164–181, 2019, doi: 10.1016/j.eswa.2019.01.040.
[55] X. Xu et al., “Distributed Temporal Link Prediction Algorithm based on Label Propagation,” Futur. Gener. Comput. Syst., vol. 93, pp. 627–636, 2019, doi: 10.1016/j.future.2018.10.056.
[56] Z. Wang, J. Liang, and R. Li, “A Fusion Probability Matrix Factorization Framework for Link Prediction,” Knowledge-Based Syst., vol. 159, no. June, pp. 72–85, 2018, doi: 10.1016/j.knosys.2018.06.005.
[57] P. K. Sharma, S. Rathore, and J. H. Park, “Multilevel learning based modeling for link prediction and users’ consumption preference in Online Social Networks,” Futur. Gener. Comput. Syst., vol. 93, pp. 952–961, 2019, doi: 10.1016/j.future.2017.08.031.
[1] [58] E. Alpaydin, Introduction to machine learning, 3rd ed. London: The MIT Press, pp. 640, August, 2014, available at :https://mitpress.mit.edu/9780262028189/introduction-to-machine-learning/
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
___________________________________________________________
International Journal of Advances in Intelligent Informatics
ISSN 2442-6571 (print) | 2548-3161 (online)
Organized by UAD and ASCEE Computer Society
Published by Universitas Ahmad Dahlan
W: http://ijain.org
E: info@ijain.org (paper handling issues)
andri.pranolo.id@ieee.org (publication issues)
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0