Link predictability of complex network from spectrum perspective

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

doi:10.7498/aps.69.20191817

Journals >Acta Physica Sinica >Volume 69 >Issue 8 >Page 088901-1 > Article

Acta Physica Sinica
Vol. 69, Issue 8, 088901-1 (2020)

Link predictability of complex network from spectrum perspective

Suo-Yi Tan¹, Ming-Ze Qi², Jun Wu^3、*, and Xin Lu^1、*

Author Affiliations

¹College of Systems Engineering, National University of Defense Technology, Changsha 410073, China

²College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China

³International Academic Center of Complex Systems, Beijing Normal Univerdity, Zhuhai 519087, China

show less

DOI: 10.7498/aps.69.20191817 Cite this Article

Suo-Yi Tan, Ming-Ze Qi, Jun Wu, Xin Lu. Link predictability of complex network from spectrum perspective[J]. Acta Physica Sinica, 2020, 69(8): 088901-1 Copy Citation Text

show less

Fig. 1. Illustration of link prediction problem

Download full size | View in the Article

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

Download full size | View in the Article

Fig. 3. The link predictability of model network versus

with various

Download full size | View in the Article

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

Download full size | View in the Article

Fig. 5. The performance of prediction algorithms in real networks

Download full size | View in the Article

网络	$ 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

Table 1.

Performance of link prediction algorithms in model 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

Table 2.

Basic statistics of 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

Table 3.

The precision of link prediction algorithms in real networks

链路预测算法在真实网络中的precision值

Suo-Yi Tan, Ming-Ze Qi, Jun Wu, Xin Lu. Link predictability of complex network from spectrum perspective[J]. Acta Physica Sinica, 2020, 69(8): 088901-1

Download Citation

Tools

Save the article for my favorites

Paper Information