1. College of Information and Communication Engineering, Dalian Nationalities University, Dalian 116600, China; 2. Web Science Center, University of Electronic Science and Technology of China, Chengdu 610054, China
Abstract：Link predictability in complex networks refers to the upper limit for link prediction accuracy by using prediction algorithm, and the analysis of link predictability is conductive to compare the pros and cons for various prediction methods in theory. In this paper, we analyzed the topological distance distribution between two nodes forming a link during the process of multiple networks evolution, and then illustrated the mechanism for making effective link prediction based on common neighbor similarity index. At last, we analyzed the prediction upper limit （predictability) for nine algorithms based on common neighbor similarity in theory. By analyzing the limitation of first order neighbor prediction algorithm and the factor affecting link predictability, we proposed two types of link prediction algorithms based on high order path information and calculated their predictability index. This study proposed the link predictability index in theory, and proved the validity of the proposed link prediction algorithm by predicting real networks.
[1] 吕琳媛. 复杂网络链路预测[J]. 电子科技大学学报, 2010,39（5):651-661. Lü Linyuan. Link prediction on complex network[J]. Journal of University of Eletronic Science and Technology of China, 2010,39（5):651-661. [2] Lü L, Zhou T. Link prediction in complex networks:a survey[J]. Physica A, 2011, 390（6):1150-1170. [3] Guimerà R, Sales-Pardo M. Missing and spurious interactions and the reconstruction of complex networks[J]. Proc Natl Acad Sci USA, 2009, 106（52), 22073-22078. [4] Clauset A, Moore C. Newman M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008,453（7191):98-101. [5] Wang W Q, Zhang Q M, Zhou T. Evaluating network models:a likelihood analysis[J]. EPL, 2012, 98（2):28004. [6] 刘宏鲲, 吕琳媛, 周涛. 利用链路预测推断网络演化机制[J]. 中国科学:物理学, 力学, 天文学, 2011, 41（7):816-823. Liu Hongkun, Lü Linyuan, Zhou Tao. Uncovering the network evolution mechanism by link prediction[J]. Science in China Series G:Physics Mechanics & Astronomy, 2011,41（7):816-823. [7] Liben-Nowell D, Kleinberg J. The link prediction problem for social networks[C]//Proceedings of the Twelfth International Conference on Information and Knowledge Management. New Orleans, 2003:556-559. [8] Getoor L, Diehl C P. Link mining:a survey[J]. ACM SIGKDD Explorations Newsletter, 2005, 7（2):3-12. [9] Sarukkai R R. Link prediction and path analysis using Markov chains[J]. Computer Networks, 2000, 33（1):377-386. [10] Zhu J, Hong J, Hughes J G. Using Markov chains for link prediction in adaptive web sites[C]//Proceedings of the International Conference on Soft-Ware:Computing in an Imperfect World. Berlin, 2002:60-73. [11] Popescul A, Ungar L. Statistical relational learning for link prediction[C]//Workshop on Learning Statistical Models from Relational Data. New York:ACM Press, 2003. [12] Yu K, Chu W, Yu S, et al. Stochastic relational models for discriminative link prediction[DB/OL].[2013-03-20]. http://www.gatsby.ucl.ac.uk/~chuwei/paper/gplink_nips06.pdf. [13] Zhang L, Hu K, Tang Y. Predicting disease-related genes by topological similarity in human protein-protein interaction network[J]. Cent Eur J Phys, 2009,8（4):672-682. [14] Zhou T, Lü L, Zhang Y C. Predicting missing links via local information[J]. Eur Phys J B, 2009, 71（4):623-630. [15] 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（4):046122. [16] Lü L, Zhou T. Link prediction in weighted networks:The role of weak ties[J]. EPL, 2010, 89（1):18001. [17] Milo R, Shen-Orr S, Itzkovitz S, et al. Network motifs:simple building blocks of complex networks[J]. Science, 2002, 298（5594):824-827. [18] Xu X K, Zhang J, Small M. Superfamily phenomena and motifs of networks induced from time series[J]. Proc Natl Acad Sci USA, 2008, 105（50):19601-19605. [19] Zhang Q M, Lü L, Wang W Q, et al. Potential theory for directed networks[J]. PLoS One, 2013, 8:e55437. [20] 王林, 商超. 无标度网络中的链路预测问题研究[J]. 计算机工程, 2012, 38（3):67-70. Wang Lin, Shang Chao. Research on link prediction problem in scale-free network[J]. Computer Engineering, 2012,38（3):67-70.
