Abstract：In link prediction, the similarity indices based on random walk process often set the probability of particles transferring to adjacent nodes to be equal, but neglecting the influence of node degree on the transition probability. To save this problem, a link prediction algorithm of biased random walk with restart is proposed. Firstly, we redefine the transfer probability of particles by referring to biased random walk. Then we apply it to the random walk with restart to explore the effect of node degree on the transfer of particles. Finally, on the basis of biased random walk,the proposed index is compared with six classical similarity indices.The experimental results of six real data sets show that the prediction algorithm of biased random walk with restart has higher prediction accuracy than that the unbiased one, and is better than other similarity indices.
吕亚楠, 韩华, 贾承丰, 瞿倩倩. 基于有偏向的重启随机游走链路预测算法[J]. 复杂系统与复杂性科学, 2018, 15(4): 17-24.
Ly Ya′nan, HAN Hua, JIA Chengfeng, QU Qianqian. Link Prediction Algorithm Based on Biased Random Walk with Restart. Complex Systems and Complexity Science, 2018, 15(4): 17-24.
[1]Costa L F, Rodrigues F A, Travieso G, et al. Characterization of complex networks: a survey of measurements[J]. Advnces in Physics. 2007,56(1):167242. [2]Cannistraci C V, Alanis-Lobato G, Ravasi T. From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks[J]. Sci Rep, 2013, 3(4):1613. [3]Ma C, Zhou T, Zhang H F. Playing the role of weak clique property in link prediction:a friend recommendation model[J]. Sci Rep, 2016, 6:30098. [4]刘宏鲲, 吕琳媛, 周涛. 利用链路预测推断网络演化机制[J]. 中国科学:物理学, 力学, 天文学, 2011, 41(7):816823. Liu Hongkun, Lü Linyuan, Zhou Tao. Uncovering the network evolution mechanism by link prediction [J]. Sci Sin Phys Mech Astron, 2011, 41: 816823. [5]Lü L Y, Zhou T. Link Prediction in complex networks:a survey[J]. Physica A:Statistical Mechanics and Its Applications, 2011, 390(6):11501170. [6]Wu Z, Lin Y, Wang J, et al. Link prediction with node clustering coefficient[J]. Physica A Statistical Mechanics & Its Applications, 2016, 452:18. [7]Yang Y, Zhang J, Zhu X, et al. Link prediction via significant influence[J]. Physica A Statistical Mechanics & Its Applications, 2018, 492:15231530. [8]Peng Z, Wang F, Xiang W, et al. The reconstruction of complex networks with community structure[J]. Sci Rep, 2015, 5:17287. [9]Klein D J,Randic M.Resistance distance[J].Journal of Mathematical Chemistry,1993,12(1):8195. [10]Brin S,Page L.The anatomy of a large-scale hypertextual web search engine[J].Computer network and ISDN Systems,1998,30(1):107117. [11]Jeh G, Widom J. SimRank: a measure of structural-context similarity[C]∥Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA:ACM, 2002:538543. [12]Park H, Jung J, Kang U. A comparative study of matrix factorization and random walk with restart in recommender systems [C]∥IEEE, International Conference on Big Data. Boston, USA: IEEE, 2017:756765. [13]Jung J, Jin W, Sael L, et al. Personalized ranking in signed networks using signed random walk with restart[C]∥IEEE, International Conference on Data Mining. Barcelona, Spain: IEEE, 2017:973978. [14]Zhu Z A, Lattanzi S, Mirrokni V. A local algorithm for finding well-connected clusters[J].ICML, 2013:396404. [15]Li R H, Yu J X, Liu J. Link prediction: the power of maximal entropy random walk[C]∥ACM International Conference on Information and Knowledge Management. Glasgow, United Kingdom: ACM, 2011:11471156. [16]刘思, 刘海, 陈启买, 等. 基于网络表示学习与随机游走的链路预测算法[J]. 计算机应用, 2017, 37(8):22342239. Liu Si, Liu Hai, Chen Qimai, et al. Link prediction algorithm based on network representation learning and random walk[J]. Journal of Computer Applications, 2017, 37(8):22342239. [17]Jin W, Jung J, Kang U. Supervised and extended restart in random walks for ranking and link prediction in networks[DB/OL]. [20180803]. https://arxiv.org/pdf/1710.06609v1.pdf. [18]Vázquez A, Moreno Y. Resilience to damage of graphs with degree correlations[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2003, 67(1):015101. [19]Fawcett T. An introduction to ROC analysis[J]. Pattern Recognition Letters, 2006, 27(8):861874. [20]Fronczak A, Fronczak P. Biased random walks in complex networks: the role of local navigation rules[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics, 2009, 80(1):016107. [21]徐全智. 随机过程及应用[M]. 北京:高等教育出版社, 2013. [22]郑伟, 王朝坤, 刘璋, 等. 一种基于随机游走模型的多标签分类算法[J]. 计算机学报, 2010, 33(8):14181426. Zheng Wei, Wang Chaokun, Liu Zhang, et al. A multi-label classification algorithm based on random walk model[J]. Chinese Journal of Computers, 2010, 33(8):14181426. [23]Liu W, Lu L. Link prediction based on local random walk[J]. Physics, 2010, 89(5):5800758012. [24]Network data[EB/OL]. [20180803].http://www-personal.umich.edu/~mejn/netdata. [25]Barabási A L, Alber R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439):509512. [26]Adamic L A, Adar E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3):211230.
