A Novel Link Prediction Approach on Social Networks
Subject Areas : electrical and computer engineeringS. Rezavandi Shoaii 1 , H. Zare 2
1 - University of Tehran
2 - University of Tehran
Abstract :
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.
