روشی نوین برای پیش‌بینی ارتباط در شبکه‌های اجتماعی ناهمگن
محورهای موضوعی : مهندسی برق و کامپیوترسعیده رضاوندی شعاعی 1 , هادی زارع 2 *
1 - دانشگاه تهران
2 - دانشگاه تهران
کلید واژه: اندازه شباهت پیش‌بینی ارتباط شبکه‌های اجتماعی شبکه‌های اجتماعی ناهمگن کاوش ارتباطات یادگیری با ناظر,
چکیده مقاله :
با گسترش روزافزون شبکه‌های اجتماعی، علوم شبکه مورد توجه بسیاری از پژوهشگران در زمینه‌های مختلف قرار گرفته است. علاوه بر آن بسیاری از مسایل کاربردی مهندسی با استفاده از ابزار شبکه‌های اجتماعی مدل‌سازی شده‌اند. پیش‌بینی تغییر و تحول در ساختار شبکه‌های اجتماعی یکی از مسایل اساسی در تحلیل شبکه‌های اجتماعی است که با عنوان مسأله پیش‌بینی ارتباط در علوم شبکه شناخته می‌شود. امروزه با گسترش استفاده از شبکه‌های اجتماعی، فعالیت افراد در قالب چندین شبکه با عنوان شبکه‌های اجتماعی ناهمگن رواج پیدا کرده است. پیش‌بینی ارتباط در شبکه‌های اجتماعی ناهمگن را می‌توان بر اساس اطلاعات اضافی موجود نسبت به روش‌های قبلی مورد بهبود قرار داد. در رویکرد پیشنهادی این مقاله، ابتدا یک معیار شباهت جدید برای کاربران در شبکه‌های ناهمگن بر اساس توسعه روش‌های مطرح پیشین و با در نظر گرفتن ارتباط بین لایه‌های مختلف معرفی می‌شود، سپس با استفاده از رویکرد یادگیری باناظر و بهره‌گیری از ویژگی‌های تولیدشده بر مبنای معیار شباهت معرفی‌شده، الگوریتم پیشنهادی مورد تشریح قرار می‌گیرد. برای ارزیابی روش پیشنهادی از معیارهای استاندارد همانند دقت و صحت بهره گرفته‌ایم. مقایسه روش پیشنهادی با روش‌های شناخته‌شده پیشین بر روی مجموعه داده‌های مختلف نشان می‌دهد که روش پیشنهادی ما برای پیش‌بینی ارتباط از عملکرد بهتر و مطلوب‌تری برخوردار است به طوری که از نظر صحت تا ۲۰ درصد موجب بهبود عملکرد شده است.
Nowadays the network science has been attracted many researchers from a wide variety of different fields and many problems in engineering domains are modelled through social networks measures. One of the most important problems in social networks is the prediction of evolution and structural behavior of the networks that is known as link prediction problem in the related literature. Nowadays people use multiple and different social networks simultaneously and it causes to demonstrate a new domain of research known as heterogenous social networks. There exist a few works on link prediction problem on heterogenous networks. In this paper, first a novel similarity measure for users in heterogenous networks is defined. Then a novel link prediction algorithm is described through a supervised learning approach which is consisted by the generated features from the introduced similarity measures. We employ the standard evaluation criteria for verification of the proposed approach. The comparison of the proposed algorithm to the other well-known earlier works showed that our proposed method has better performance than the other methods based on testing on several network datasets.
[1] M. Newman, Networks: An Introduction, Oxford, New York: Oxford University Press, 2010.
[2] M. Al Hasan, V. Chaoji, S. Salem, and M. Zaki, "Link prediction using supervised learning," in Proc. 4th Workshop on Link Analysis, Counter-Terrorism and Security, SDM’06, 10 pp., 2006.
[3] A. Anil, et al., "Link prediction using social network analysis over heterogeneous terrorist network," in Proc. IEEE Int.l Conf. on Smart City/SocialCom/SustainCom (SmartCity), Chengdu, China, 19-21 Dec. 2015.
[4] L. M. Aiello, et al., "Friendship prediction and homophily in social media," ACM Trans. Web, vol. 6, no. 2, Article No. 9, Jun. 2012.
[5] L. Lu, C. H. Jin, and T. Zhou, "Similarity index based on local paths for link prediction of complex networks," Phys. Rev. E, vol. 80, no. 4, pp. 046122, 26 Oct. 2009.
[6] F. Folino and C. Pizzuti, "Link prediction approaches for disease networks," in Proc. Int. Conf. on Information Technology in Bio- and Medical Informatics, ITBAM ‘11, pp. 99-108, Toulouse, France, 31 Aug.- 1 Sept., 2011.
[7] N. Rummele, R. Ichise, and H. Werthner, "Exploring supervised methods for temporal link prediction in heterogeneous social networks," in Proc. of the 24th Int. Conf. on World Wide Web, pp. 1363-1368, Florence, Italy, 18-22 May 2015.
[8] C. A. Bliss, M. R. Frank, C. M. Danforth, and P. S. Dodds, "An evolutionary algorithm approach to link prediction in dynamic social networks," J. Comput. Sci., vol. 5, no. 5, pp. 750-764, Sept. 2014.
[9] P. Wang, B. Xu, Y. Wu, and X. Zhou, "Link prediction in social networks: the state-of-the-art," Sci. China Inf. Sci., vol. 58, no. 1, pp. 1-38, Jan. 2015.
[10] F. Liu and S. T. Xia, "Link prediction in aligned heterogeneous networks," in T. Cao, et al. (eds) Advances in Knowledge Discovery and Data Mining, LNCS, vol 9077. pp. 33-44, Springer, Cham, 2015.
[11] G. D. Lyu, C. J. Fan, L. F. Yu, B. X. Xiu, and W. M. Zhang, "Predicting missing links via structural similarity," Int. J. Mod. Phys. B, vol. 29, no. 15, Article No. 1550095, Apr. 2015.
[12] M. Jalili, Y. Orouskhani, M. Asgari, N. Alipourfard, and M. Perc, "Link prediction in multiplex online social networks," Open Sci., vol. 4, no. 2, Article No. 160863, Feb. 2017.
[13] Y. Yang, N. Chawla, Y. Sun, and J. Hani, "Predicting links in multi-relational and heterogeneous networks," in Proc. of the IEEE 12th Int. Conf. on Data Mining, pp. 755-764, Washington, DC, USA, 10-13 Dec. 2012.
[14] G. Rossetti, M. Berlingerio, and F. Giannotti, "Scalable link prediction on multidimensional networks," in Proc. IEEE 11th Int. Conf. on Data Mining Workshops, ICDMW’11, pp. 979-986, Vancouver, Canada, 11-11 Dec. 2011.
[15] J. Leskovec and J. D. Ullman, Mining of Massive Datasets, 2nd Ed., Cambridge: Cambridge University Press, 2014.
[16] 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, May 2007.
[17] M. E. J. Newman, "Clustering and preferential attachment in growing networks," Phys. Rev. E, vol. 64, no. 2, 4 pp., Jul. 2001.
[18] V. Martinez, F. Berzal, and J. C. Cubero, "A survey of link prediction in complex networks," ACM Comput Surv., vol. 49, Article No. 69, Dec. 2016.
[19] T. Sorensen, "A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on danish commons," Biol Skr, vol. 5, pp. 1-34, 1948.v [20] L. Katz, "A new status index derived from sociometric analysis," Psychometrika, vol. 18, no. 1, pp. 39-43, Mar. 1953.
[21] F. Fouss, A. Pirotte, J. M. Renders, and M. Saerens, "Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation," IEEE Trans. Knowl. Data Eng., vol. 19, no. 3, pp. 355-369, Mar. 2007.
[22] G. Jeh and J. Widom, "SimRank: a measure of structural-context similarity," in Proc. of the 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 538-543, Edmonton, Alberta, Canada, 23-26 Jul. 2002.
[23] D. Davis, R. Lichtenwalter, and N. V. Chawla, "Multi-relational link prediction in heterogeneous information networks," in Proc. Int. Conf. on Advances in Social Networks Analysis and Mining, pp. 281-288, Kaohsiung, Taiwan, 25-27 Jul. 2011.
[24] J. Zhang, P. S. Yu, and Z. H. Zhou, "Meta-path based multi-network collective link prediction," in Proc. of the 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1286-1295, New York, NY, USA, 24-27 Aug. 2014.
[25] B. R. Memon and U. K. Wiil, "Predicting links in multi-relational networks," in Proc. IEEE Joint Intelligence and Security Informatics Conf., JISIC’14, pp. 107-114, Hague, The Netherlands, 24-26 Sept. 2014.
[26] Y. Sun, J. Han, X. Yan, P. S. Yu, and T. Wu, "Pathsim: meta path-based top-k similarity search in heterogeneous information networks," in Proc. VLDB Endow., vol. 4, no 11, pp. 992-1003, 2011.
[27] J. Tang, T. Lou, and J. Kleinberg, "Inferring social ties across heterogenous networks," in Proc. of the 5th ACM Int. Conf. on Web Search and Data Mining, pp. 743-752, Seattle, Washington, USA, 8-12 Feb. 2012.
[28] D. Li, Y. Zhang, Z. Xu, D. Chu, and S. Li, "Exploiting information diffusion feature for link prediction in Sina Weibo," Sci. Rep., vol. 6, Article No. 20058, Jan. 2016.
[29] J. Li, B. Ge, K. Yang, Y. Chen, and Y. Tan, "Meta-path based heterogeneous combat network link prediction," Phys. Stat. Mech. Its Appl., vol. 482, no. Supplement C, pp. 507-523, 15 Sep. 2017.
[30] M. Pujari and R. Kanawati, "Link prediction in multiplex networks," NHM, vol. 10, no. 1, pp. 17-35, 2015.
[31] C. Yang, J. Sun, J. Ma, S. Zhang, G. Wang, and Z. Hua, "Scientific collaborator recommendation in heterogeneous bibliographic networks," in Proc. 48th Hawaii Int. Conf. on System Sciences, HICSS’15, pp. 552-561, Kauai, HI, USA, 5-8 Jan. 2015.
[32] L. A. Adamic and E. Adar, "Friends and neighbors on the web," Soc. Netw., vol. 25, no. 3, pp. 211-230, Jul. 2003.
[33] The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition, New York, NY: Springer, 2016.
[34] K. P. Murphy, Machine Learning: A Probabilistic Perspective, MIT Press, 2012.
[35] S. Haykin, Neural Networks: A Comprehensive Foundation, 1st Ed. Upper Saddle River, NJ, USA: Prentice Hall PTR, 1994.
[36] C. C. Chang and C. J. Lin, "LIBSVM: a library for support vector machines," ACM Trans. Intell. Syst. Technol. TIST, vol. 2, no. 3, Article No. 27, Apr. 2011.
[37] C. Bishop, Pattern Recognition and Machine Learning, New York: Springer, 2007.
[38] J. Coleman, E. Katz, and H. Menzel, "The diffusion of an innovation among physicians," Sociometry, vol. 20, no. 4, pp. 253-270, Dec. 1957.
[39] M. De Domenico, A. Lancichinetti, A. Arenas, and M. Rosvall, "Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems," Phys. Rev. X 5, arXiv:1408.2925 2015.
[40] J. Friedman, T. Hastie, and R. Tibshirani, The Elements of Statistical Learning, 2nd Ed., Berlin: Springer Series in Statistics, 2011.
[41] M. Ranjbar, P. Moradi, M. Azami, and M. Jalili, "An imputation-based matrix factorization method for improving accuracy of collaborative filtering systems," Eng. Appl. Artif. Intell., vol. 46, Issue A, pp. 58-66, Nov. 2015.v [42] L. Yao, L. Wang, L. Pan, and K. Yao, "Link prediction based on common-neighbors for dynamic social network," in Proc. 7th Int. Conf. Ambient Syst. Netw. Technol. ANT 2016 6th Int. Conf. Sustain. Energy Inf. Technol. SEIT-2016 Affil. Workshop, vol. 83, Supplement C, pp. 82-89, Jan. 2016.
[43] Y. Dong, N. V. Chawla, and A. Swami, "Metapath2Vec: scalable representation learning for heterogeneous networks," in Proc. of the 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 135-144, Halifax, NS, Canada, 13-17 Aug. 2017.
[44] E. Zhong, E. W. Xiang, W. Fan, N. N. Liu, and Q. Yang, Friendship Prediction in Composite Social Networks, ArXiv Prepr. ArXiv: 14024033, 2014.
[45] B. Pachev and B. Webb, Fast Link Prediction for Large Networks Using Spectral Embedding, ArXiv Prepr. ArXiv: 1703.09693, 2017.