基于分形特性的复杂网络全局效率估计方法

doi:10.11959/j.issn.1000-436x.2020118

摘要/Abstract

摘要：

针对大型网络中效率计算时间复杂度高、计算耗时长的问题，提出一种基于分形特性的网络效率估计方法。利用复杂网络拓扑结构的分形特性，分析网络效率与节点关联和的关系，用部分节点关联和来估计网络全局效率。此外，为了快速判断复杂网络的分形特性，提出基于节点关联和的分形特性判别方法。在构造网络和真实网络中进行实验分析，结果表明，所提方法能准确有效地估算网络全局效率，比原始的网络效率计算方法可缩减不低于90%的计算时间。

关键词: 复杂网络, 网络效率, 分形, 关联和

Abstract:

A method of network efficiency estimation based on fractal property was proposed for solving the problems of high complexity and time-consuming calculation of efficiency in large scale networks.Considering the fractal properties of complex network topology,the relationship between network efficiency and node correlation sum was analyzed,and the global network efficiency was estimated by partial nodes.Besides,to rapidly find the fractal properties of complex networks,a fractal property discrimination method based on node correlation sum was proposed.The experimental analysis in the construction network and the real-world network show that the proposed method can accurately and effectively estimate the global efficiency of the network,which reduces the calculation time by at least 90% compared with the original method.

Key words: complex network, network efficiency, fractal, correlation sum

中图分类号:

O157.5

张胜,戴维凯,吴锋,蓝文祥. 基于分形特性的复杂网络全局效率估计方法[J]. 通信学报, 2020, 41(7): 204-212.

Sheng ZHANG,Weikai DAI,Feng WU,Wenxiang LAN. Global efficiency estimation method of complex network based on fractal property[J]. Journal on Communications, 2020, 41(7): 204-212.

图/表 11

图1

表1

图2

图3

图4

表2

图5

表3

图6

表4

真实道路网络效率估计"

道路网络	节点数	边数	r_k	决定系数R²	关联维数	P_f	n_k	T_save	估计值 $\hat{E}$	理论值E	相对误差
犹他州	242 432	288 982	578	0.995	2.02	0.954	1 815	99.30%	0.004 027	0.004 026	0.03%
威斯康星州	514 687	623 277	503	0.995	1.91	0.868	3 088	99.40%	0.003 625	0.003 602	0.64%
路易斯安那州	413 574	495 392	660	0.995	1.85	0.916	1 836	99.60%	0.003 171	0.003 173	0.06%

表4

图7

参考文献 37

[1]	BARABáSI A L , PóSFAI M . Network science[M]. Cambridge: Cambridge University PressPress, 2016.
[2]	LATORA V , MARCHIORI M . Efficient behavior of small-world networks[J]. Physical Review Letters, 2001,87(19): 3-6.
[3]	HéBERT-DUFRESNE L , ALLARD A , YOUNG J ,et al. Global efficiency of local immunization on complex networks[J]. Scientific Reports, 2013,(3):2171.
[4]	AVENA-KOENIGSBERGER A , MISIC B , SPORNS O . Communication dynamics in complex brain networks[J]. Nature Reviews Neuroscience, 2018,19(1): 17-33.
[5]	BEATY R E , KAUFMAN S B , BENEDEK M ,et al. Personality and complex brain networks:the role of openness to experience in default network efficiency[J]. Human brain mapping, 2016,37(2): 773-779.
[6]	周漩, 张凤鸣, 周卫平 ,等. 利用节点效率评估复杂网络功能鲁棒性[J]. 物理学报, 2012,61(19): 1-7.
	ZHOU X , ZHANG F P , ZHOU W P ,et al. Evaluating complex network functional robustness by node efficiency[J]. Acta Physica Sinica, 2012,61(19): 1-7
[7]	EK B , VERSCHNEIDER C , NARAYAN D A . Efficiency of star-like graphs and the Atlanta subway network[J]. Physica A:Statistical Mechanics and Its Applications, 2013,392(21): 5481-5489.
[8]	ZHANG L , QIN J , HE Y ,et al. Network-level optimization method for road network maintenance programming based on network efficiency[J]. Journal of Central South University, 2015,22(12): 4882-4889.
[9]	LATORA V , MARCHIORI M . Economic small-world behavior in weighted networks[J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2003,32(2): 249-263.
[10]	BOMPARD E , WU D , XUE F . Structural vulnerability of power systems:a topological approach[J]. Electric Power Systems Research, 2011,81(7): 1334-1340.
[11]	WANG S , DU Y , DENG Y . A new measure of identifying influential nodes:efficiency centrality[J]. Communications in Nonlinear Science and Numerical Simulation, 2017(47): 151-163.
[12]	WANG Y , WANG S , DENG Y . A modified efficiency centrality to identify influential nodes in weighted networks[J]. Pramana, 2019,92(4):68.
[13]	HOUGARDY S . The Floyd-Warshall algorithm on graphs with negative cycles[J]. Information Processing Letters, 2010,110(8-9): 279-281.
[14]	SONG C , HAVLIN S , MAKSE H A . Self-similarity of complex networks[J]. Nature, 2005,433(7024): 392-395.
[15]	SONG C , HAVLIN S , MAKSE H A . Origins of fractality in the growth of complex networks[J]. Nature Physics, 2006,2(4): 275-281.
[16]	DUAN S , WEN T , JIANG W . A new information dimension of complex network based on Rényi entropy[J]. Physica A:Statistical Mechanics and Its Applications, 2019(516): 529-542.
[17]	LEI M , LIU L , WEI D . An improved method for measuring the complexity in complex networks based on structure entropy[J]. IEEE Access, 2019,(7): 159190-159198.
[18]	ROSENBERG E . Maximal entropy coverings and the information dimension of a complex network[J]. Physics Letters A, 2017,381(6): 574-580.
[19]	ZHANG Q , LI M , DENG Y . Measure the structure similarity of nodes in complex networks based on relative entropy[J]. Physica A:Statistical Mechanics and Its Applications, 2018(491): 749-763.
[20]	SHANKER O . Defining dimension of a complex network[J]. Modern Physics Letters B, 2007,21(6): 321-326.
[21]	SHANKER O . Graph zeta function and dimension of complex network[J]. Modern Physics Letters B, 2007,21(11): 639-644.
[22]	WEI D , WEI B , ZHANG H ,et al. A generalized volume dimension of complex networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2014,2014(10):P10039.
[23]	WEN T , JIANG W . An information dimension of weighted complex networks[J]. Physica A:Statistical Mechanics and Its Applications., 2018(501): 388-399.
[24]	PU J , CHEN X , WEI D ,et al. Identifying influential nodes based on local dimension[J]. Europhysics Letters, 2014,107(1):10010.
[25]	BIAN T , DENG Y . Identifying influential nodes in complex networks:A node information dimension approach[J]. Chaos:an Interdisciplinary Journal of Nonlinear Science, 2018,28(4):43109.
[26]	WEN T , DENG Y . Identification of influencers in complex networks by local information dimensionality[J]. Information Sciences, 2020(512): 549-562.
[27]	WEN T , PELUSI D , DENG Y . Vital spreaders identification in complex networks with multi-local dimension[J]. Knowledge-Based Systems, 2020:105717.
[28]	关世杰, 赵海 . 互联网中路由级和IP级拓扑分形特征分析[J]. 通信学报, 2013,34(11): 162-170.
	GUAN S J , ZHAO H . Analysis of fractal characteristic of internet router-level and IP-level topology[J]. Journal on Communications, 2013,34(11): 162-170.
[29]	DIJKSTRA E W . A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959,1(1): 269-271.
[30]	SONG C , GALLOS L K , HAVLIN S ,et al. How to calculate the fractal dimension of a complex network:the box covering algorithm[J]. Journal of Statistical Mechanics:Theory and Experiment, 2007,2007(3):P03006.
[31]	LACASA L , GóMEZ-GARDE?ES J . Correlation dimension of complex networks[J]. Physical Review Letters, 2013,110(16): 1-5.
[32]	WANG X , LIU Z , WANG M . The correlation fractal dimension of complex networks[J]. International Journal of Modern Physics C, 2013,24(5):1350033.
[33]	姜建国, 曹建中, 高玉明 . 信号与系统分析基础[M]. 北京: 清华大学出版社, 2006.
	JIANG J G , CAO J Z , GAO Y M . Fundamentals of signal and system analysis[M]. Beijing: Tsinghua University PressPress, 2006.
[34]	EK B , VERSCHNEIDER C , NARAYAN D A . Global efficiency of graphs[J]. AKCE International Journal of Graphs and Combinatorics, 2015,12(1): 1-13.
[35]	ACHARD S , BULLMORE E . Efficiency and cost of economical brain functional networks[J]. PLOS Computational Biology, 2007,3(2):e17.
[36]	CLAUSET A , SHALIZI C R , NEWMAN M E J . Power-law distributions in empirical data[J]. SIAM Review, 2009,51(4): 661-703.
[37]	KITSAK M , HAVLIN S , PAUL G ,et al. Betweenness centrality of fractal and nonfractal scale-free model networks and tests on real networks Maksim[J]. Physical Review E, 2007,75(5):056115.

统计量	r = 1	r = 2	r = 3	r = 4	r = 5
A_i(r)	8	21	36	44	46
S_i(r)	8	13	15	8	2

分形程度e	r_k	决定系数R²	关联维数	P_f	n_k	T_save	估计值ê	理论值E	相对误差
0	24	0.998	1.46	92.20%	142	89%	0.084 9	0.085 6	0.82%
0.2	16	0.998	1.84	87.80%	104	92%	0.105 2	0.106 3	1.04%
0.4	11	0.998 6	2.23	80.50%	104	92%	0.124 3	0.125 8	1.19%
0.6	7	0.998 4	2.66	66.20%	155	88%	0.152 9	0.152 3	0.39%
0.8	5	0.998 1	3.09	57.10%	129	90%	0.169 7	0.168 3	0.83%
1.0	5	0.998 4	3.46	54.30%	142	89%	0.188 4	0.189 9	0.79%

连边概率p	r_k	决定系数R²	关联维数	P_f	n_k	T_save	估计值ê	理论值E	相对误差
0	626	1	0.998	100%	100	98%	0.011 2	0.011 2	0%
0.2	5	0.995 9	4.6	70.70%	450	91%	0.203 9	0.203 3	0.30%
0.4	4	0.998 8	5.09	64.30%	300	94%	0.241 7	0.241 2	0.21%
0.6	4	0.999 8	5.18	88.30%	100	98%	0.264	0.264 2	0.08%
0.8	3	0.997 3	5.58	38.60%	400	92%	0.280 7	0.281 2	0.18%
1.0	3	0.995 6	5.7	51.30%	150	97%	0.294 1	0.293 8	0.10%