Computer Science ›› 2016, Vol. 43 ›› Issue (6): 199-203.doi: 10.11896/j.issn.1002-137X.2016.06.040

Previous Articles     Next Articles

Link Prediction in Networks with Node Attributes Based on Random Walks Algorithm

CHEN Yong-xiang and CHEN Ling   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Link prediction is an important area in complex network analysis.It is widely used in various domains such as sociology,anthropology,information science and computer science.A link prediction algorithm was proposed based on link similarity score propagation by a random walk in networks with node attributes.In the algorithm,each link in the network is assigned a transmission probability according to the similarity of the attributes on the nodes connected by taking a link.The similarity of the attributes on the nodes is also treated as the initial value of their link similarity.The link similarity between the nodes is then propagated by the random walk in the network according to their transmission probability.At last,the link similarity is just the final score of link prediction.Our experimental results show that the proposed algorithm can obtain more accurate results than other algorithms in the networks with node attributes.

Key words: Link prediction,Attributes,Random walks,Complex networks

[1] Lichtenwalter R N.New precepts and method in link prediction[C]∥Proceedings of ACM KDD’10.2010:243-252
[2] Lü Lin-yuan,Zhou Tao.Link prediction in complex networks:A survey[J].Physica A,2011,390:1150-1170
[3] Lü Lin-yuan.Link Prediction on Complex Networks[J].Journal of University of Electronic Science and Technology,2010,39(5):651-661(in Chinese) 吕琳媛.复杂网络链路预测[J].电子科技大学学报,2010,39(5):651-661
[4] Zhang L,Hu K,Tang Y.Predicting Disease-related Genes byTopological Similarity in Human Protein-Protein Interaction Network[J].Central European Journal of Physics,2010,8(4):672-682
[5] Guimera R,Sales-Pardo M.Missing and Spurious Interactionsand the Reconstruction of Complex Networks[J].Proceedings of the National Academy of Science,2010,106(52):22073-22078
[6] Papadimitriou A,Symeonidis P,Manolopoulos Y.Fast and accurate link prediction in social networking systems[J].Journal of Systems and Software,2012,85(9):2119-2132
[7] Bao Zhi-feng,Zeng Yong,Tay Y C.sonLP:social network link prediction by principal component regression[C]∥Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.2013:364-371
[8] Fournet J,Barrat A.Contact patterns among high school stu-dents[J].PLoS ONE,2014,9(9):e107878
[9] Sun Y,Barbery R,Gupta M,et al.Co-Author Relationship Prediction in Heterogeneous Bibliographic Networks[C]∥Procee-dings of 2011 International Conference on Advances in Social Networks Analysis and Mining,2011(ASONAM’2011).2011:121-128
[10] Li Xin,Chen H.Recommendation as link prediction in bipartite graphs:A graph kernel-based machine learning approach[J].Decision Support Systems,2013,4(2):880-890
[11] Huang Z,Lin D K J.The time-series link prediction problem with applications in communication surveillance[J].INFORMS J.on Computing,2009,1:286-303
[12] Liu Hong-kun,Lv Lin-yuan,Zhou Tao.Uncovering the network evolution mechanism by link prediction[J].China Sciences:Astronomy,Physics Mechanics,2011,1(7),816-823(in Chinese) 刘宏鲲,吕琳媛,周涛.利用链路预测推断网络演化机制[J].中国科学:物理学力学天文学,2011,1(7):816-823
[13] Salton G,Mcgill M J.Introduction to modern information re-trieval[M].Auckland:MuGraw-Hill,1983
[14] Jaccard P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin de la Société Vaudoise des Science Naturelles,1901,37:547-579
[15] Sorensen T.A method of establishing groups of equalamplitude in plant sociology based on similarity of species content and its application to analyses of the vegetation on Danish commons[J].Biol Skr,1948,5(4):1-34
[16] Ravasz E,Somera A L,Mongru D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1553-1555
[17] Leicht E A,Holme P,Newman M E J.Vertex similarity in networks[J].Phys Rev E,2006,73:026120
[18] Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512
[19] Adamic L A,Adar E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230
[20] Zhou T,Lv L,Zhang Y C.Predicting missing links via local information[J].Eur Phys J B,2009,71(4):623-630
[21] Lü L,Jin C H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Phys Rev E,2009,80:046122
[22] Katz L.A new status index derived from sociometric analysis[J].Psychometrika,1953,18(1):39-43
[23] Klein D J,Randic M.Resistance distance[J].J Math Chem,1993,12(1):81-95
[24] Fouss F,Pirotte A,Renders J M,et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].IEEE Trans Knowl Data Eng,2007,19(3):355-369
[25] Brin S,Page L.The anatomy of a large-scale hypertextual Web search engine[J].Comput Netw & ISDN Syst,1998,30(1-7):107-117
[26] Jeh G,Widom J.SimRank:A measure of structural context similarity[C]∥Proceedings of the ACM SIGKDD 2002.New York:ACM Press,2002:538-543
[27] Zhou T,Lv L,Zhang Y C.Predicting missing links via local information[J].European Physical Journal B,2009,1(4):623-630
[28] Lv L,Jin C H,Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Physical Review E-Statistical,Nonlinear,and Soft Matter Physics,2009,0(4):046122
[29] Liu W P,Lv L.Link Prediction Based on Local Random Walk[J].European Physics Letter,2010,89:58007
[30] Rao Jun,Wu Bin,Dong Yu-xiao.Parallel Link Prediction in Com-plex Networkunder Use MapReduce [J].Journal of Software,2012,3(12):3175-3186(in Chinese) 饶君,吴斌,东昱晓.MapReduce环境下的并行复杂网络链路预测[J].软件学报,2012,3(12):3175-3186
[31] Dong Yu-xiao,Ke Qing,Wu Bin.Link Prediction Based on NodesSimilarity[J].Computer Science,2011,8(7):162-164(in Chinese) 东昱晓,柯庆,吴斌.基于节点相似性的链接预测[J].计算机科学,2011,8(7):162-164
[32] Lv L Y,Zhou T.Link prediction in complex networks:A survey[J].Physica A,2011,390:1150-1170
[33] Ahmed H S,Faouzi B M,Caelen J.Detection and classification of the behavior of people in an intelligent building by camera[J].International Journal on Smart Sensing and Intelligent Systems,September 2013,6(4):1317-1342
[34] Yang L T,Wang S,Jiang H.Cyclic Temporal Network Density and its impact on Information Diffusion for Delay Tolerant Networks[J].International Journal on Smart Sensing and Intelligent Systems,2011,4(1):35-52
[35] Liu Z H,Ma J F,Zeng Y.Secrecy transfer for sensor networks:from random graphs to secure random geometric graphs[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(1):77-94
[36] Jia X,Xin F,Chuan W R.Adaptive spray routing for opportunistic networks[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(1):95-119
[37] Sarkar P,Chakrabarti D,Jordan M I.Nonparametric Link Prediction in Dynamic Networks[C]∥Proceedings of the 29th International Conference on Machine Learning.Edinburgh,Scotland,UK,2012
[38] He Yu-lin,Liu J N K,Hu Yan-xing,et al.OWA operator based link prediction ensemble for social network[J].Expert Systems with Applications,2015,42(1):21-50
[39] Barbieri N,Bonchi F,Manco G.Who to follow and why:link prediction with explanations[C]∥Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2014:1266-1275
[40] Bliss C A,Frank M R,Danforth C M.Peter Sheridan Dodds,An evolutionary algorithm approach to link prediction in dynamic social networks[J].Journal of Computational Science,2014,5(5):750-764
[41] Cao Bin,Liu Nan,Yang Qiang.Transfer Learning for Collective Link Prediction in Multiple,Heterogenous Domains[C]∥Proceedings of the International Conference on Machine Learning.2010:159-166
[42] Melville P,Sindhwani V.Recommender systems[C]∥Encyclopedia of Machine Learning.Springer,2010
[43] Bartunov S,Korshunov A,Park S T,et al.Joint link-attributeuser identity resolution in online social networks[C]∥Procee-dings of the Workshop on Social Network Mining and Analysis (SNA-KDD).2012
[44] Bliss C A,Frank M R,Danforth C M.Peter Sheridan Dodds,An evolutionary algorithm approach to link prediction in dynamic social networks[J].Journal of Computational Science,2014,5(5):750-764
[45] Li X,Chen H C.Recommendation as link prediction in bipartite graphs:A graph kernel-based machine learning approach[J].Decision Support Systems,2013,4(2):880-890
[46] Zeng Z Z,Chen Ke-jia,Zhang Shao-bo,et al.A link prediction approach using semi-supervised learning in dynamic networks[C]∥2013 Sixth International Conference on Advanced Computational Intelligence (ICACI).2013:276-280
[47] Backstrom L,Leskovec J.Supervised random walks:Predicting and recommending links in social networks[C]∥Proceedings of the WSDM Conference.2010:635-644
[48] Menon A KElkan C.Link prediction via matrix factorization[C]∥Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD).2011:437-452
[49] Hu F Y,Wong H S.Labelling of Human Motion Based on CBGA and Probabilistic Model[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(2):583-609
[50] Jia X,Xin F,Chuan W R.Adaptive spray routing for opportunistic networks[J].International Journal on Smart Sensing and Intelligent Systems,2013,6(1):95-119
[51] Kang C,Pugliese A,Grant J,et al.STUN:querying spatio-temporal uncertain(social) networks[J].Social Network Analysis &Mining,2014,4(1):1-19
[52] Backstrom L,Leskovec J.Supervised random walks Predictingand recommending links in social networks[C]∥Proceedings of the WSDM Conference.2010:635-644
[53] Luong N T,Nguyen T T,Jung J J,et al.Discovering Co-author Relationship in Bibliographic Data Using Similarity Measures and Random Walk Model[J].Intelligent Information and Database Systems,Lecture Notes in Computer Science,2015,1:127-136

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!