A spectral coarse graining algorithm based on relative distance

Qing-Lin Yang; Li-Fu Wang; Huan Li; Mu-Zhou Yu

doi:10.7498/aps.68.20181848

Journals >Acta Physica Sinica >Volume 68 >Issue 10 >Page 100501-1 > Article

Acta Physica Sinica
Vol. 68, Issue 10, 100501-1 (2019)

A spectral coarse graining algorithm based on relative distance

Qing-Lin Yang, Li-Fu Wang^*, Huan Li, and Mu-Zhou Yu

DOI: 10.7498/aps.68.20181848 Cite this Article

Qing-Lin Yang, Li-Fu Wang, Huan Li, Mu-Zhou Yu. A spectral coarse graining algorithm based on relative distance[J]. Acta Physica Sinica, 2019, 68(10): 100501-1 Copy Citation Text

show less

Fig. 1. The processing of merging nodes.合并节点的过程

Download full size | View in the Article

Fig. 2. Two schemes of merging 15 nodes into 14 nodes.15个节点并为14个节点的两种方案

Download full size | View in the Article

Fig. 3. The maintaining of obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network. 采用ISCG与ISCGR算法获得谱粗粒化网络对的保持情况　(a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

Download full size | View in the Article

Fig. 4. The maintaining of obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network. 采用ISCG算法与ISCGR算法获得谱粗粒化网络对的保持情况 (a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

Download full size | View in the Article

Fig. 5. The maintaining of obtained by using ISCG and ISCGR algorithms for real-world networks in coarse graining network. 分别采用ISCG与ISCGR算法对实际网络进行粗粒化后保持情况的对比图

Download full size | View in the Article

种类	网络	节点	边	文献	Δλ₂ (30%N)		Δλ₂ (20%N)		Δλ₂ (10%N)		Δλ₂ (2%N)
种类	网络	节点	边	文献	ISCG	ISCGR	ISCG	ISCGR	ISCG	ISCGR	ISCG	ISCGR
化学	DD_g1	327	899	[27]	2.06%	1.77%	7.66%	7.17%	34.90%	23.46%	187%	173%
化学	DD_g1046	707	1646	[27]	1.40%	1.31%	7.27%	6.62%	42.92%	17.81%	191%	94%
合作	netscience	379	914	[27]	0.13%	0.13%	1.05%	1.05%	5.79%	5.46%	49.74%	39.41%
合作	ca-GrQc	4158	13422	[27]	0	0	0	0	0.03%	0.03%	0.34%	0.20%
社交	ia-infect-dublin	410	2765	[27]	0.91%	0.95%	3.59%	2.46%	13.47%	14.37%	104%	51%
	moreno_crime	829	1473	[28]	0.01%	0.01%	0.39%	0.24%	3.02%	2.32%	13.34%	13.05%
	socfb-Sim81	1518	32988	[28]	0	0	0	0	0	0	23.65%	11.82%
	ia-email-univ	1133	5451	[27]	0	0	0	0	0.07%	0.06%	0.26%	0.16%
电力	东北电网	58	70	[29]	8.14%	5.78%	24.36%	18.63%	54.65%	54.65%	—	—
	IEEE162	162	280	[29]	2.35%	2.10%	16.94%	8.68%	27.70%	25.65%	113%	113%
	IEEE145	145	422	[29]	0.85%	0.80%	4.14%	3.16%	17.85%	14.22%	240%	230%
生物	diseasome	516	1188	[27]	0.22%	0.11%	0.79%	0.67%	2.58%	2.02%	33.45%	15.82%
互联网	Route views	6474	12572	[28]	0	0	0	0	0.07%	0.07%	1.07%	0.57%
互联网	Wiki-vote	889	2914	[27]	0.02%	0.01%	0.07%	0.05%	0.17%	0.17%	0.61%	0.49%
技术	bibd_12_4	495	2951	[27]	0.02%	0.01%	0.20%	0.06%	0.80%	0.41%	29.02%	19.73%
	G1	800	19176	[27]	0	0	0	0	0.27%	0.19%	0.56%	0.55%
	GD00_c	638	1020	[27]	0.02%	0.02%	0.27%	0.27%	1.50%	1.15%	4.29%	2.75%
	dwt_1005	1005	3808	[27]	2.17%	0.49%	4.25%	1.61%	23.93%	10.83%	129%	92%
	dwt_503	503	2762	[27]	4.94%	3.68%	9.33%	6.18%	44.00%	21.32%	138%	117%
数学	130bit	584	6058	[27]	0.01%	0	0.02%	0.01%	0.68%	0.36%	1.51%	1.15%
	ash608	608	1212	[27]	0.74%	0.40%	6.95%	1.10%	18.29%	13.73%	51.99%	30.57%
	bibd_12_5	792	7860	[27]	0.02%	0	0.07%	0.03%	0.35%	0.11%	25.14%	5.84%
	jagmesh3	1089	3136	[27]	0.31%	0.10%	1.44%	1.13%	16.86%	9.25%	192%	127%
	frb45-21-1	945	386854	[27]	0.03‱	0	0.23‱	0.04‱	0.51‱	0.28‱	1.39‱	1.34‱
	kneser_6_2_1	676	2017	[27]	0.03%	0.01%	0.16%	0.13%	1.83%	0.44%	81%	30%
	EX1	560	4368	[27]	0	0	0.03%	0.03%	3.08%	0.41%	123%	26%
随机	G43	1000	9990	[27]	0	0	0.01%	0	0.13%	0.11%	0.95%	0.50%

Table 1. The Statistics table of maintaining obtained by using ISCG and ISCGR algorithms for some real-world networks in coarse graining network. 分别采用ISCG和ISCGR算法对实际网络约简后的保持情况统计表

Qing-Lin Yang, Li-Fu Wang, Huan Li, Mu-Zhou Yu. A spectral coarse graining algorithm based on relative distance[J]. Acta Physica Sinica, 2019, 68(10): 100501-1

Download Citation

Tools

Save the article for my favorites

Paper Information