استفاده از مدل های طبقه بندی برای بهینه سازی پیش بینی لینک در شبکه های اجتماعی خودمحور
محورهای موضوعی : مهندسی الکترونیک
سهیلا نعمتی
1
,
مهدی صادق زاده
2
,
مازیار گنجو
3
1 - گروه مهندسی کامپیوتر، دانشکده فنی و مهندسی، دانشگاه آزاد اسلامی واحد بوشهر، بوشهر، ایران
2 - گروه مهندسی کامپیوتر، دانشکده برق و کامپیوتر، واحد ماهشهر، دانشگاه آزاد اسلامی، ماهشهر، ایران
3 - گروه مهندسی کامپیوتر، دانشکده فنی مهندسی، دانشگاه آزاد اسلامی واحد بوشهر، بوشهر، ایران
کلید واژه: استخراج ویژگی, Feature extraction, معیار شباهت, شبکه های اجتماعی خودمحور, طبقه بندی داده ها, Ego-social networks, Similarity criterion, Data classification,
چکیده مقاله :
سیستم های پیشنهاد دهنده اجتماعی، نسل جدیدی از این سیستم ها می باشند که از شبکه اجتماعی به عنوان بستر مدل سازی کاربر استفاده می کنند تا با استفاده از حجم غنی داده های تعاملی، برخی از چالش ها را مرتفع نمایند. شبکه های آنلاین اجتماعی، دوستان جدید را به کاربران ثبت شده بر مبنای خصوصیات گراف محلی پیشنهاد می دهند. هدف اصلی مسئله پیش بینی لینک در شبکه های اجتماعی، پیشنهاد لیستی از کاربران به یک کاربر خاص می باشد که احتمالا در آینده با آنها ارتباط برقرار خواهد کرد. در این تحقیق یک روش پیش بینی لینک بر اساس خصوصیات مدل های طبقه بندی ارائه شده است. در اینجا مسئله پیش بینی لینک به یک مسئله طبقه بندی با دو کلاس مثبت و منفی تبدیل شده، جائیکه کلاس مثبت نشان دهنده ارتباط و کلاس منفی نشان دهنده عدم ارتباط دو کاربر است. سه طبقه بند کلاسیک DT، NN و NB برای کار طبقه بندی استفاده شده است. برای ایجاد مجموعه داده از ویژگی های اعتبار، خوش بینی، تعداد همسایه های مشترک، تعداد مسیر با طول های متفاوت، تعداد توئییت های مشترک، تعداد مسیرهای خود محور داخلی و خارجی بهره گرفته می شود. اگر چه شبکه های خودمحور همپوشانی زیادی در حلقه ها ندارند، اما آزمایش ها نشان می دهد که در نظر گرفتن اطلاعات مسیرهای خودمحور به طور قابل توجهی عملکرد پیش بینی را بهبود می بخشد. طبقه بندی DT بهترین عملکرد را با دقت متوسط 99.85% به ثبت رسانیده است.
Social propositional systems are a new generation of systems that use the social network as a user modeling platform to maximize some challenges by using rich interactive data volumes. To make Social networking sites offer new friends to registered users based on local graph features. The main purpose of the link prediction problem on social networks is to suggest a list of users to a particular user that they will probably be communicating in the future. In this research, a prediction method for the link is presented based on the characteristics of classification models. Here, the prediction problem of the link is transformed into a classifying problem with two positive and negative classes, where the positive class represents the relationship and the negative class indicates that the two users are not communicating. Three classical classes DT, NN and NB are used for classification work. To create the dataset, the features of credibility, optimism, number of neighbors, the number of paths of different lengths, the number of shared tweets, the number of internal and external axes are used. Although self-centered grids do not have much overlap in the rings, experiments show that the consideration of self-directed pathways significantly improves predictive performance. The DT classification has recorded the best performance with an average accuracy of 99.85%.
[1] 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.
[2] T. E. Webster, “The Need to Engage With Smartphones and Social Network Sites (SNSs) at Korean Universities,” Recent Developments in Technology-Enhanced and Computer-Assisted Language Learning, pp. 122–143, 2020.
[3] K. Li, L. Tu, and L. Chai, “Ensemble-model-based link prediction of complex networks,” Computer Networks, vol. 166, pp. 106978, 2020.
[4] Y. Sada, J. Hou, P. Richardson, H. El-Serag, and J. Davila, “Validation of Case Finding Algorithms for Hepatocellular Cancer From Administrative Data and Electronic Health Records Using Natural Language Processing,” Medical Care, vol. 54, no. 2, 2016.
[5] S.Samanta, and M. Pal, “Link Prediction in Social Networks,” Graph Theoretic Approaches for Analyzing Large-Scale Social Networks, 164. 2017
[6] S.Rafiee, C.Salavati, and A. Abdollahpouri, “CNDP: Link prediction based on common neighbors degree penalization,” Physica A: Statistical Mechanics and its Applications, vol.539, pp.122950, 2020.
[7] D. Liben-Nowell, and J. Kleinberg, “The Link-prediction Problem for Social Networks,” Journal of the American Society for Information Science and Technology, vol.58, no.7, pp.1019-1031, 2007.
[8] H. Mohammad, “Link Prediction In Social Networks, Indiana university,” Social Network Data Analytics, pp. 243-275, 2011.
[9] 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, pp.160863, 2017.
[10] W.Cui, C.Pu, Z.Xu, S.Cai, J.Yang, and A.Michaelson, , “Bounded link prediction in very large networks,” Physica A: Statistical Mechanics and its Applications, vol.457, pp.202-214, 2016.
[11] 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, pp.535, 2016.
[12] F. Liu, B.Liu, C.Sun, M.Liu, and X. Wang, “Deep belief network-based approaches for link prediction in signed social networks,” Entropy, vol.17, no.4, pp.2140-2169, 2015.
[13] R.Laishram, K.Mehrotra, and C. K. Mohan, “Link Prediction in Social Networks with Edge Aging,” In proc.In Tools with Artificial Intelligence (ICTAI), November 2016, pp. 606-613.
[14] M.Naderipour,S.Bastani, and M. F.Zarandi, “A Type-2 Fuzzy Model for Link Prediction in Social Network. World Academy of Science, Engineering and Technology,” International Journal of Computer, Electrical, Automation, Control and Information Engineering,” vol.10, no.7, pp.1355-1360, 2016.
[15] P. L. Szczepański, 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 proc Twenty-Fourth International Joint Conference on Artificial Intelligence , June 2015, pp. 638-644.
[16] 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, pp.12261, 2015.
[17] S.Han, and Y. Xu, “Link Prediction in Microblog Network Using Supervised Learning with Multiple Features, ” in JCP, vol.11, no.1, pp.72-82, 2016.
[18] M.Zhang, , Z.Cui, , S.Jiang, and Y.Chen, “Beyond Link Prediction: Predicting Hyperlinks in Adjacency Space, ” AAAI-2018 , pp. 4430-4437, 2018.
[19] Z.Huo, X.Huang, and X. Hu, “Link Prediction with Personalized Social Influence,” in proc.Conference on Artificial Intelligence, 2018, pp. 136-139.
[20] P.Pei, B.Liu, and L. Jiao, “Link prediction in complex networks based on an information allocation index,” Physica A: Statistical Mechanics and its Applications, vol.470, pp.1-11, 2017.
[21] J.Leskovec, and J.Mcauley, “Learning to discover social circles in ego networks,” In Advances in neural information processing systems, pp. 539-547, 2012.
[22] K. K.Shang, , M.Small, , X. K.Xu, and W. S. Yan, “The role of direct links for link prediction in evolving networks,” EPL (Europhysics Letters), vol.117, no.2, pp.28002, 2017.
[23] S.Sharma, and A.Singh, “An efficient method for link prediction in weighted multiplex networks,” Computational Social Networks, vol.3, no. 1, pp.7, 2016.
[24] A.Anagnostopoulos, J.Łącki, S. Lattanzi, S. Leonardi, and M. Mahdian, “Community detection on evolving graphs,” In Advances in Neural Information Processing Systems, pp. 3522-3530, 2016.
[25] 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
[26] L.Bai, X.Cheng, J. Liang, and Y.Guo, “Fast graph clustering with a new description model for community detection,” Information Sciences, vol. 388- 389, pp. 37-47, 2017.
[27] F.Aghabozorgi, and M.R.Khayyambashi, “A new similarity measure for link prediction based on local structures in social networks,” Physica A: Statistical Mechanics and its Applications, vol.501, pp.12-23. 2018
[28] X.Cao, Y.Zheng, C.Shi, J.Li, & B.Wu, “Meta-path-based link prediction in schema-rich heterogeneous information network,” International Journal of Data Science and Analytics, vol.3, no.4, pp.285-296, 2017.
_||_[1] 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.
[2] T. E. Webster, “The Need to Engage With Smartphones and Social Network Sites (SNSs) at Korean Universities,” Recent Developments in Technology-Enhanced and Computer-Assisted Language Learning, pp. 122–143, 2020.
[3] K. Li, L. Tu, and L. Chai, “Ensemble-model-based link prediction of complex networks,” Computer Networks, vol. 166, pp. 106978, 2020.
[4] Y. Sada, J. Hou, P. Richardson, H. El-Serag, and J. Davila, “Validation of Case Finding Algorithms for Hepatocellular Cancer From Administrative Data and Electronic Health Records Using Natural Language Processing,” Medical Care, vol. 54, no. 2, 2016.
[5] S.Samanta, and M. Pal, “Link Prediction in Social Networks,” Graph Theoretic Approaches for Analyzing Large-Scale Social Networks, 164. 2017
[6] S.Rafiee, C.Salavati, and A. Abdollahpouri, “CNDP: Link prediction based on common neighbors degree penalization,” Physica A: Statistical Mechanics and its Applications, vol.539, pp.122950, 2020.
[7] D. Liben-Nowell, and J. Kleinberg, “The Link-prediction Problem for Social Networks,” Journal of the American Society for Information Science and Technology, vol.58, no.7, pp.1019-1031, 2007.
[8] H. Mohammad, “Link Prediction In Social Networks, Indiana university,” Social Network Data Analytics, pp. 243-275, 2011.
[9] 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, pp.160863, 2017.
[10] W.Cui, C.Pu, Z.Xu, S.Cai, J.Yang, and A.Michaelson, , “Bounded link prediction in very large networks,” Physica A: Statistical Mechanics and its Applications, vol.457, pp.202-214, 2016.
[11] 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, pp.535, 2016.
[12] F. Liu, B.Liu, C.Sun, M.Liu, and X. Wang, “Deep belief network-based approaches for link prediction in signed social networks,” Entropy, vol.17, no.4, pp.2140-2169, 2015.
[13] R.Laishram, K.Mehrotra, and C. K. Mohan, “Link Prediction in Social Networks with Edge Aging,” In proc.In Tools with Artificial Intelligence (ICTAI), November 2016, pp. 606-613.
[14] M.Naderipour,S.Bastani, and M. F.Zarandi, “A Type-2 Fuzzy Model for Link Prediction in Social Network. World Academy of Science, Engineering and Technology,” International Journal of Computer, Electrical, Automation, Control and Information Engineering,” vol.10, no.7, pp.1355-1360, 2016.
[15] P. L. Szczepański, 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 proc Twenty-Fourth International Joint Conference on Artificial Intelligence , June 2015, pp. 638-644.
[16] 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, pp.12261, 2015.
[17] S.Han, and Y. Xu, “Link Prediction in Microblog Network Using Supervised Learning with Multiple Features, ” in JCP, vol.11, no.1, pp.72-82, 2016.
[18] M.Zhang, , Z.Cui, , S.Jiang, and Y.Chen, “Beyond Link Prediction: Predicting Hyperlinks in Adjacency Space, ” AAAI-2018 , pp. 4430-4437, 2018.
[19] Z.Huo, X.Huang, and X. Hu, “Link Prediction with Personalized Social Influence,” in proc.Conference on Artificial Intelligence, 2018, pp. 136-139.
[20] P.Pei, B.Liu, and L. Jiao, “Link prediction in complex networks based on an information allocation index,” Physica A: Statistical Mechanics and its Applications, vol.470, pp.1-11, 2017.
[21] J.Leskovec, and J.Mcauley, “Learning to discover social circles in ego networks,” In Advances in neural information processing systems, pp. 539-547, 2012.
[22] K. K.Shang, , M.Small, , X. K.Xu, and W. S. Yan, “The role of direct links for link prediction in evolving networks,” EPL (Europhysics Letters), vol.117, no.2, pp.28002, 2017.
[23] S.Sharma, and A.Singh, “An efficient method for link prediction in weighted multiplex networks,” Computational Social Networks, vol.3, no. 1, pp.7, 2016.
[24] A.Anagnostopoulos, J.Łącki, S. Lattanzi, S. Leonardi, and M. Mahdian, “Community detection on evolving graphs,” In Advances in Neural Information Processing Systems, pp. 3522-3530, 2016.
[25] 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
[26] L.Bai, X.Cheng, J. Liang, and Y.Guo, “Fast graph clustering with a new description model for community detection,” Information Sciences, vol. 388- 389, pp. 37-47, 2017.
[27] F.Aghabozorgi, and M.R.Khayyambashi, “A new similarity measure for link prediction based on local structures in social networks,” Physica A: Statistical Mechanics and its Applications, vol.501, pp.12-23. 2018
[28] X.Cao, Y.Zheng, C.Shi, J.Li, & B.Wu, “Meta-path-based link prediction in schema-rich heterogeneous information network,” International Journal of Data Science and Analytics, vol.3, no.4, pp.285-296, 2017.