-
Link prediction in complex networks has attracted much attention in recent years and most of work focuses on proposing more accurate prediction algorithms. In fact, “how difficultly the target network can be predicted” can be regarded as an important attribute of the network itself. In this paper it is intended to explain and characterize the link predictability of the network from the perspective of spectrum. By analyzing the characteristic spectrum of the network, we propose the network link predictability index. Through calculating the index, it is possible to learn how difficultly the target network can be predicted before choosing algorithm, and to solve the problem whether the network is unpredictable or the algorithm is inappropriate. The results are useful for the selecting and matching the complex network and link prediction algorithms.
-
Keywords:
- link predictability /
- link prediction /
- spectrum theory /
- complex network
[1] Albert R, Jeong H, Barabási A L 2000 Nature 406 378
Google Scholar
[2] Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47
Google Scholar
[3] Newman M E J 2003 SIAM Rev. 45 167
Google Scholar
[4] Wang X F 2002 Int. J. Bifurcat. Chaos 12 885
Google Scholar
[5] 侯绿林, 老松杨, 肖延东, 白亮 2015 物理学报 64 188901
Google Scholar
Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901
Google Scholar
[6] 吕琳媛 2010 电子科技大学学报 39 651
Google Scholar
Lü L L 2010 J. Univ. Electron. Sci. Technol. China 39 651
Google Scholar
[7] 吕琳媛, 周涛 2013 链路预测 (北京: 高等教育出版社) 第 41页
Lü L L, Zhou T 2013 Link Prediction (Beijing: Higher Education Press) p41 (in Chinese)
[8] Sarukkai R R 2010 Comput. Networking 33 377
[9] Clauset A, Moore C, Newman M E J 2008 Nature 453 98
Google Scholar
[10] Guimerá R, Marta S P 2009 Proc. Natl. Acad. Sci. U.S.A. 106 22073
Google Scholar
[11] Pan L M, Zhou T, Lü L Y, Hu C K 2016 Sci. Rep. 6 22955
Google Scholar
[12] Taskar B, Wong M F, Abbeel P, Koller D 2003 Proceedings of the 16th International Conference on Neural Information Processing Systems (Cambridge: MIT Press) pp659–666
[13] David L N, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019
Google Scholar
[14] Zhou T, Lü L Y, Zhang Y C 2009 Eur. Phys. J. B 71 623
Google Scholar
[15] 许小可, 方锦清 2010 复杂系统与复杂性科学 7 116
Google Scholar
Xu X K, Fang J Q 2010 Complex Syst. Complex Sci. 7 116
Google Scholar
[16] Tan S Y, Wu J, Lü L Y, Li M J, Lu X 2016 Sci. Rep. 6 22916
Google Scholar
[17] Amaral L A N 2008 Proc. Natl. Acad. Sci. U.S.A. 105 6795
Google Scholar
[18] Menche J, Sharma A, Kitsak M, Ghiassian S D, Vidal M, Loscalzo J, Barabási A L 2015 Science 347 1257601
Google Scholar
[19] Lü L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
Google Scholar
[20] 朱郁筱, 吕琳媛 2012 电子科技大学学报 41 163
Zhou Y X, Lü L Y 2012 J. Univ. Electron. Sci. Technol. China 41 163
[21] 刘宏鲲, 吕琳媛, 周涛 2011 中国科学: 物理学 力学 天文学 41 816
Google Scholar
Liu H K, Lü L Y, Zhou T 2011 Scientia Sinica: Phys. Mech. Astron. 41 816
Google Scholar
[22] Zhang Q M, Lü L Y, Wang W Q, X Y, Zhou T 2013 PLoS One 8 1
[23] Wang W Q, Zhang Q M, Zhou T 2012 EPL 98 28004
Google Scholar
[24] Zhang Q M, Xu X K, Zhu Y X, Zhou T 2015 Sci. Rep. 5 10350
Google Scholar
[25] Lü L Y, Zhou T 2011 Physica A 390 1150
Google Scholar
[26] 于会, 刘尊, 李勇军, 尹超 2016 物理学报 65 020501
Google Scholar
Yu H, Liu Z, Li Y J, Yi C 2016 Acta Phys. Sin. 65 020501
Google Scholar
[27] 许小可, 许爽, 朱郁筱, 张千明 2014 复杂系统与复杂性科学 11 41
Xu X K, Xu S, Zhu Y X, Zhang Q M 2014 Complex Syst. Complex Sci. 11 41
[28] Lü L Y, Pan L M, Zhou T, Zhang Y C, Stanley H E 2015 Proc. Natl. Acad. Sci. USA 112 2325
Google Scholar
[29] Yin L K, Zheng H Y, Bian T, Deng Y 2014 Physica A 482 699712
[30] Hanley J A, McNeil B J 1982 Radiology 143 29
Google Scholar
[31] Herlocker J L, Konstan J A, Terveen L G, Riedl J T 2004 ACM Trans. Inf. Syst. 22 5
Google Scholar
[32] Zhou T, Ren J, Matúš M, Zhang Y C 2007 Phys. Rev. E 76 046115
Google Scholar
[33] Farkas I J, Derényi I, Barabási A L, Vicsek T 2001 Phys. Rev. E 64 026704
Google Scholar
[34] Estrada E, Hatano N, Benzi M 2012 Phys. Rep. 514 89
Google Scholar
[35] Newman M E J 2006 Phys. Rev. E 74 036104
Google Scholar
[36] Kousik D, Sovan S, Madhumangal P 2018 Soc. Netw. Anal. Min. 8 1
Google Scholar
[37] 张金浩, 申玉卓, 李艳雨, 孙娟, 李晓霞 2017 物理学报 66 188901
Google Scholar
Zhang J H, Shen Y Z, Li Y Y, Sun J, Li X X 2017 Acta Phys. Sin. 66 188901
Google Scholar
[38] Wang R, Lin P, Liu M X, Wu Y, Zhou T, Zhou C S 2019 Phys. Rev. Lett. 123 038301
Google Scholar
[39] Estrada E 2006 EPL 73 649
Google Scholar
[40] Tan S Y, Wu J, Li M J, Lu X 2016 EPL 114 58002
Google Scholar
[41] Estrada E, Hatano N 2007 Chem. Phys. Lett. 439 247
Google Scholar
-
图 1 链路预测问题示意图
Figure 1. Illustration of link prediction problem
图 2 无标度网络特征谱直方图
Figure 2. The histograms of eigenvalues of random sacle-free networks
图 3 不同节点规模下, 模型网络可预测性
$ p $ 随$ \alpha $ 的变化Figure 3. The link predictability of model network versus
$ \alpha $ with various$ N $ 
图 4 无标度网络和随机网络可预测性示意图
Figure 4. The link predictability of BA scale-free network and random graph
图 5 预测算法在真实网络上的表现
Figure 5. The performance of prediction algorithms in real networks
表 1 链路预测算法在模型网络中的表现
Table 1. Performance of link prediction algorithms in model networks.
网络 $ p $ CN AA RA LP IA CAR PA Katz RWR ACT LRW LHN-II BA网络 0.975 0.423 0.324 0.272 0.415 0.271 0.283 0.594 0.412 0.136 0.507 0.085 0.003 随机网络 0.543 0.015 0.008 0.009 0.008 0.009 0 0.030 0.008 0.002 0.020 0 0.001 
DownLoad: CSV
表 2 不同领域真实网络拓扑属性
Table 2. Basic statistics of real networks.
网络 V E r $\langle k\rangle$ $\langle l\rangle$ C C_elegans 297 2148 –0.163 14.47 2.46 0.308 Windsurfers 43 336 –0.147 15.63 1.70 0.564 Adolescent health 2539 12969 0.251 10.22 4.52 0.142 Jazz 198 2742 0.020 27.69 2.21 0.520 USAirport 1574 28236 –0.113 35.87 3.14 0.384 Metabolic 453 4596 –0.226 20.29 2.64 0.124 Yeast 2375 11693 0.454 9.85 5.10 0.388 US powergrid 4941 6594 0.003 2.67 20.09 0.103 Physicians 241 1098 –0.056 9.11 3.02 0.552 Air Traffic Control 1226 2615 –0.015 4.27 6.10 0.063 Contiguous USA 49 107 0.233 4.37 4.26 0.406 Email 1133 5451 0.078 9.62 3.65 0.166 King James Bible 1773 9131 –0.048 10.30 3.38 0.163 Protein Stelzl 1706 6207 –0.191 7.28 5.09 0.006 Router 5022 6258 –0.138 2.49 6.45 0.033
DownLoad: CSV
表 3 链路预测算法在真实网络中的precision值
Table 3. The precision of link prediction algorithms in real networks
网络 p CN AA RA LP IA CAR PA Katz RWR ACT LRW SRW C_elegans 0.999 0.100 0.107 0.105 0.101 0.108 0.094 0.058 0.101 0.105 0.055 0.110 0.108 Windsurfers 0.999 0.379 0.396 0.413 0.370 0.393 0.381 0.214 0.369 0.360 0.247 0.402 0.426 Adolescent health 0.422 0.103 0.103 0.088 0.089 0.101 0.094 0.003 0.088 0.053 0.008 0.042 0.047 Jazz 1.000 0.502 0.523 0.542 0.489 0.535 0.517 0.133 0.489 0.352 0.168 0.342 0.393 USAirport 0.998 0.333 0.336 0.364 0.332 0.332 0.330 0.280 0.332 0.087 0.294 0.076 0.080 Metabolic 0.999 0.137 0.195 0.269 0.141 0.168 0.132 0.104 0.141 0.196 0.092 0.214 0.215 Yeast 0.998 0.154 0.177 0.267 0.158 0.161 0.148 0.094 0.174 0.073 0.211 0.045 0.059 US powergrid 0.362 0.054 0.032 0.028 0.058 0.047 0.037 0.000 0.057 0.016 0.034 0.015 0.018 Physicians 0.368 0.119 0.126 0.121 0.117 0.122 0.106 0.014 0.117 0.119 0.015 0.132 0.127 Air Traffic Control 0.480 0.036 0.024 0.018 0.037 0.021 0.025 0.007 0.037 0.002 0.015 0.002 0.002 Contiguous USA 0.540 0.096 0.130 0.132 0.005 0.000 0.000 0.012 0.004 0.067 0.053 0.133 0.121 Email 0.950 0.144 0.158 0.143 0.142 0.159 0.145 0.018 0.141 0.065 0.024 0.052 0.051 King James Bible 0.960 0.167 0.270 0.446 0.163 0.256 0.176 0.078 0.163 0.186 0.069 0.197 0.224 Protein Stelzl 0.441 0.001 0.002 0.001 0.001 0.002 0.006 0.014 0.001 0.006 0.013 0.006 0.006 Router 0.511 0.051 0.029 0.020 0.056 0.031 0.055 0.022 0.055 0.006 0.164 0.005 0.005
DownLoad: CSV
-
[1] Albert R, Jeong H, Barabási A L 2000 Nature 406 378
Google Scholar
[2] Albert R, Barabási A L 2002 Rev. Mod. Phys. 74 47
Google Scholar
[3] Newman M E J 2003 SIAM Rev. 45 167
Google Scholar
[4] Wang X F 2002 Int. J. Bifurcat. Chaos 12 885
Google Scholar
[5] 侯绿林, 老松杨, 肖延东, 白亮 2015 物理学报 64 188901
Google Scholar
Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901
Google Scholar
[6] 吕琳媛 2010 电子科技大学学报 39 651
Google Scholar
Lü L L 2010 J. Univ. Electron. Sci. Technol. China 39 651
Google Scholar
[7] 吕琳媛, 周涛 2013 链路预测 (北京: 高等教育出版社) 第 41页
Lü L L, Zhou T 2013 Link Prediction (Beijing: Higher Education Press) p41 (in Chinese)
[8] Sarukkai R R 2010 Comput. Networking 33 377
[9] Clauset A, Moore C, Newman M E J 2008 Nature 453 98
Google Scholar
[10] Guimerá R, Marta S P 2009 Proc. Natl. Acad. Sci. U.S.A. 106 22073
Google Scholar
[11] Pan L M, Zhou T, Lü L Y, Hu C K 2016 Sci. Rep. 6 22955
Google Scholar
[12] Taskar B, Wong M F, Abbeel P, Koller D 2003 Proceedings of the 16th International Conference on Neural Information Processing Systems (Cambridge: MIT Press) pp659–666
[13] David L N, Kleinberg J 2007 J. Am. Soc. Inf. Sci. Technol. 58 1019
Google Scholar
[14] Zhou T, Lü L Y, Zhang Y C 2009 Eur. Phys. J. B 71 623
Google Scholar
[15] 许小可, 方锦清 2010 复杂系统与复杂性科学 7 116
Google Scholar
Xu X K, Fang J Q 2010 Complex Syst. Complex Sci. 7 116
Google Scholar
[16] Tan S Y, Wu J, Lü L Y, Li M J, Lu X 2016 Sci. Rep. 6 22916
Google Scholar
[17] Amaral L A N 2008 Proc. Natl. Acad. Sci. U.S.A. 105 6795
Google Scholar
[18] Menche J, Sharma A, Kitsak M, Ghiassian S D, Vidal M, Loscalzo J, Barabási A L 2015 Science 347 1257601
Google Scholar
[19] Lü L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 519 1
Google Scholar
[20] 朱郁筱, 吕琳媛 2012 电子科技大学学报 41 163
Zhou Y X, Lü L Y 2012 J. Univ. Electron. Sci. Technol. China 41 163
[21] 刘宏鲲, 吕琳媛, 周涛 2011 中国科学: 物理学 力学 天文学 41 816
Google Scholar
Liu H K, Lü L Y, Zhou T 2011 Scientia Sinica: Phys. Mech. Astron. 41 816
Google Scholar
[22] Zhang Q M, Lü L Y, Wang W Q, X Y, Zhou T 2013 PLoS One 8 1
[23] Wang W Q, Zhang Q M, Zhou T 2012 EPL 98 28004
Google Scholar
[24] Zhang Q M, Xu X K, Zhu Y X, Zhou T 2015 Sci. Rep. 5 10350
Google Scholar
[25] Lü L Y, Zhou T 2011 Physica A 390 1150
Google Scholar
[26] 于会, 刘尊, 李勇军, 尹超 2016 物理学报 65 020501
Google Scholar
Yu H, Liu Z, Li Y J, Yi C 2016 Acta Phys. Sin. 65 020501
Google Scholar
[27] 许小可, 许爽, 朱郁筱, 张千明 2014 复杂系统与复杂性科学 11 41
Xu X K, Xu S, Zhu Y X, Zhang Q M 2014 Complex Syst. Complex Sci. 11 41
[28] Lü L Y, Pan L M, Zhou T, Zhang Y C, Stanley H E 2015 Proc. Natl. Acad. Sci. USA 112 2325
Google Scholar
[29] Yin L K, Zheng H Y, Bian T, Deng Y 2014 Physica A 482 699712
[30] Hanley J A, McNeil B J 1982 Radiology 143 29
Google Scholar
[31] Herlocker J L, Konstan J A, Terveen L G, Riedl J T 2004 ACM Trans. Inf. Syst. 22 5
Google Scholar
[32] Zhou T, Ren J, Matúš M, Zhang Y C 2007 Phys. Rev. E 76 046115
Google Scholar
[33] Farkas I J, Derényi I, Barabási A L, Vicsek T 2001 Phys. Rev. E 64 026704
Google Scholar
[34] Estrada E, Hatano N, Benzi M 2012 Phys. Rep. 514 89
Google Scholar
[35] Newman M E J 2006 Phys. Rev. E 74 036104
Google Scholar
[36] Kousik D, Sovan S, Madhumangal P 2018 Soc. Netw. Anal. Min. 8 1
Google Scholar
[37] 张金浩, 申玉卓, 李艳雨, 孙娟, 李晓霞 2017 物理学报 66 188901
Google Scholar
Zhang J H, Shen Y Z, Li Y Y, Sun J, Li X X 2017 Acta Phys. Sin. 66 188901
Google Scholar
[38] Wang R, Lin P, Liu M X, Wu Y, Zhou T, Zhou C S 2019 Phys. Rev. Lett. 123 038301
Google Scholar
[39] Estrada E 2006 EPL 73 649
Google Scholar
[40] Tan S Y, Wu J, Li M J, Lu X 2016 EPL 114 58002
Google Scholar
[41] Estrada E, Hatano N 2007 Chem. Phys. Lett. 439 247
Google Scholar
DownLoad:
Catalog
Metrics
- Abstract views: 8019
- PDF Downloads: 308
- Cited By: 0
