Link predictability of complex network from spectrum perspective

Tan Suo-Yi; Qi Ming-Ze; Wu Jun; Lu Xin

doi:10.7498/aps.69.20191817

Abstract

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:

Authors and contacts

1.
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
2.
College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China
3.
International Academic Center of Complex Systems, Beijing Normal Univerdity, Zhuhai 519087, China

Corresponding author: Wu Jun, wujunpla@hotmail.com ; Lu Xin, xin.lu@flowminder.org

FullText HTML

References

[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

Cited By

图 1 链路预测问题示意图

Figure 1. Illustration of link prediction problem

DownLoad: Full-Size Img PowerPoint

图 2 无标度网络特征谱直方图

Figure 2. The histograms of eigenvalues of random sacle-free networks

DownLoad: Full-Size Img PowerPoint

图 3 不同节点规模下, 模型网络可预测性$ p $随$ \alpha $的变化

Figure 3. The link predictability of model network versus $ \alpha $ with various $ N $

DownLoad: Full-Size Img PowerPoint

图 4 无标度网络和随机网络可预测性示意图

Figure 4. The link predictability of BA scale-free network and random graph

DownLoad: Full-Size Img PowerPoint

图 5 预测算法在真实网络上的表现

Figure 5. The performance of prediction algorithms in real networks

DownLoad: Full-Size Img PowerPoint

表 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

[1]	Cui Jun-Ying, Xu Shu-Qi, Na Xu, Pan Li-Ming, Lü Lin-Yuan. Supply chain research based on complex network theory. Acta Physica Sinica, 2024, 73(19): 198901. doi: 10.7498/aps.73.20240702
[2]	Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[3]	Yang Qing-Lin, Wang Li-Fu, Li Huan, Yu Mu-Zhou. A spectral coarse graining algorithm based on relative distance. Acta Physica Sinica, 2019, 68(10): 100501. doi: 10.7498/aps.68.20181848
[4]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[5]	Zhou Jian, Jia Zhen, Li Ke-Zan. Improved algorithm of spectral coarse graining method of complex network. Acta Physica Sinica, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502
[6]	Wu Xi-Ping, Yang Hong-Yu, Han Song-Chen. Analysis on network properties of multivariate mixed air traffic management technical support system based on complex network theory. Acta Physica Sinica, 2016, 65(14): 140203. doi: 10.7498/aps.65.140203
[7]	Li Yong-Jun, Yin Chao, Yu Hui, Liu Zun. Link prediction in microblog retweet network based on maximum entropy model. Acta Physica Sinica, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
[8]	Hou Lü-Lin, Lao Song-Yang, Xiao Yan-Dong, Bai Liang. Recent progress in controllability of complex network. Acta Physica Sinica, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
[9]	Yu Xiao-Ping, Pei Tao. Analysis on degree characteristics of mobile call network. Acta Physica Sinica, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
[10]	Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[11]	Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
[12]	Liang Yi, Wang Xing-Yuan. Pinning chaotic synchronization in complex networks on maximum eigenvalue of low order matrix. Acta Physica Sinica, 2012, 61(3): 038901. doi: 10.7498/aps.61.038901
[13]	Gao Xiang-Yun, An Hai-Zhong, Fang Wei. Research on fluctuation of bivariate correlation of time series based on complex networks theory. Acta Physica Sinica, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
[14]	Gong Zhi-Qiang, Zhi Rong, Hou Wei, Wang Xiao-Juan, Feng Guo-Ling. Analysis of decadal characteristics of leading teleconnections based on complex networks theory. Acta Physica Sinica, 2012, 61(2): 029202. doi: 10.7498/aps.61.029202
[15]	Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[16]	Wang Qi-Guang, Feng Ai-Xia, Gong Zhi-Qiang, Huang Yan. Spatiotemporal analysis of information entropy of the global temperature. Acta Physica Sinica, 2011, 60(9): 099204. doi: 10.7498/aps.60.099204
[17]	Feng Guo-Lin, Zhang Lu, Zhang Da-Quan. Analysis of precursors and predictability of PDSI extremes in China. Acta Physica Sinica, 2010, 59(8): 5896-5903. doi: 10.7498/aps.59.5896
[18]	Song Qing-Song, Feng Zu-Ren, Li Ren-Hou. Multiple clusters echo state network for chaotic time series prediction. Acta Physica Sinica, 2009, 58(7): 5057-5064. doi: 10.7498/aps.58.5057
[19]	Guo Jin-Li. Impact of edges for new nodes on scale-free networks. Acta Physica Sinica, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
[20]	Wang Qi-Guang, Zhi Rong, Zhang Zeng-Ping. The research on long range correlation of Lorenz system. Acta Physica Sinica, 2008, 57(8): 5343-5350. doi: 10.7498/aps.57.5343

Catalog

Vol. 69, Issue 8 - 2020-04-20

Metrics

Abstract views: 10502
PDF Downloads: 328
Cited By: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

Search

Article

留言板