基于K-阶结构熵的网络异构性研究
|
摘要
结构熵可以考察复杂网络的异构性.为了弥补传统结构熵在综合刻画网络全局以及局部特性能力上的不足,本文依据网络节点在K步内可达的节点总数定义了K-阶结构熵,可从结构熵随K值的变化规律、最大K值下的结构熵以及网络能够达到的最小结构熵三个方面来评价网络的异构性.利用K-阶结构熵对规则网络、随机网络、Watts-Strogatz小世界网络、Barabási_-Albert无标度网络以及星型网络进行了理论研究与仿真实验,结果表明上述网络的异构性依次增强.其中K-阶结构熵能够较好地依据小世界属性来刻画小世界网络的异构性,且对星型网络异构性随其规模演化规律的解释也更为合理.此外, K-阶结构熵认为在规则结构外新增孤立节点的网络的异构性弱于未添加孤立节点的规则结构,但强于同节点数的规则网络.本文利用美国西部电网进一步论证了K-阶结构熵的有效性.
Structure entropy can evaluate the heterogeneity of complex networks, but traditional structure entropy has deficiencies in comprehensively reflecting the global and local network features. In this paper, we define a new structure entropy based on the number of the K-order neighbor nodes which refer to those nodes which a node can reach within K steps. It can be supposed that the more K-order neighbors a node has, the more important role the node plays in the network structure. Combining the formula of Shannon entropy, the K-order structure entropy can be defined and figured out to explain the differences among the relative importance among nodes. Meanwhile, the new structure entropy can describe the network heterogeneity from the following three aspects. The first aspect is the change tendency of structure entropy with the value of K. The second aspect is the structure entropy under a maximum influence scale K. The last aspect is the minimum value of the K-order structure entropy. The simulation compares the heterogeneities of five classic networks from the above three aspects, and the result shows that the heterogeneity strengthens in the from-weak-to-strong sequence: regular network, random network, WS(Watts-Strogatz) small-world network, BA(Barabási-Albert)scale-free network and star network. This conclusion is consistent with the previous theoretical research result, but hard to obtain from the traditional structure entropy. It is remarkable that the K-order structure entropy can better evaluate the heterogeneity of WS small-world networks and suggests that the greater small-world coefficients a network has, the stronger heterogeneity the network has. Besides, the K-order structure entropy can fully reflect the heterogeneity variation of star networks with network size, and reasonably explain the heterogeneity of regular networks with additional isolated nodes. It suggests that when i additional isolated nodes are added to a regular network with n nodes, the new network has weaker heterogeneity than the old one, but has stronger heterogeneity than the regular network with n+i nodes. Finally, the validity of the K-order structure entropy is further confirmed by simulations for the western power grid of the United States. Based on the minimum value of the K-order structure entropy, the heterogeneity of the western power grid is the closest to that of WS small-world networks.
Structure entropy can evaluate the heterogeneity of complex networks, but traditional structure entropy has deficiencies in comprehensively reflecting the global and local network features. In this paper, we define a new structure entropy based on the number of the K-order neighbor nodes which refer to those nodes which a node can reach within K steps. It can be supposed that the more K-order neighbors a node has, the more important role the node plays in the network structure. Combining the formula of Shannon entropy, the K-order structure entropy can be defined and figured out to explain the differences among the relative importance among nodes. Meanwhile, the new structure entropy can describe the network heterogeneity from the following three aspects. The first aspect is the change tendency of structure entropy with the value of K. The second aspect is the structure entropy under a maximum influence scale K. The last aspect is the minimum value of the K-order structure entropy. The simulation compares the heterogeneities of five classic networks from the above three aspects, and the result shows that the heterogeneity strengthens in the from-weak-to-strong sequence: regular network, random network, WS(Watts-Strogatz) small-world network, BA(Barabási-Albert)scale-free network and star network. This conclusion is consistent with the previous theoretical research result, but hard to obtain from the traditional structure entropy. It is remarkable that the K-order structure entropy can better evaluate the heterogeneity of WS small-world networks and suggests that the greater small-world coefficients a network has, the stronger heterogeneity the network has. Besides, the K-order structure entropy can fully reflect the heterogeneity variation of star networks with network size, and reasonably explain the heterogeneity of regular networks with additional isolated nodes. It suggests that when i additional isolated nodes are added to a regular network with n nodes, the new network has weaker heterogeneity than the old one, but has stronger heterogeneity than the regular network with n+i nodes. Finally, the validity of the K-order structure entropy is further confirmed by simulations for the western power grid of the United States. Based on the minimum value of the K-order structure entropy, the heterogeneity of the western power grid is the closest to that of WS small-world networks.
引文
[1]Wang X F,Li X,Chen G R 2006 Complex Network Theory and Application(Beijing:Tsinghua University Press)p8(in Chinese)[汪小帆,李翔,陈关荣2006复杂网络理论及其应用(北京:清华大学出版社)第8页]
[2]Boccaletti S,Latora V,Moreno Y,Chavez M,Hwang DU 2006 Phys.Rep.424 175
[3]Vázquez A,Dobrin R,Sergi D,Eckmann J P,Oltvai ZN,Barabási A L 2004 Proc.Natl.Acad.Sci.USA 10117940
[4]Pinto P C,Thiran P,Vetterli M 2012 Phys.Rev.Lett.109 068702
[5]Yang Y Y,Xie G 2016 Inform.Process.Manage.52 911
[6]Newman M E J 2004 Eur.Phys.J.B 38 321
[7]Lermansinkoff D B,Barch D M 2016 Neuroimage-Clin.10 96
[8]Grabow C,Grosskinsky S,Timme M 2011 Eur.Phys.J.B 84 613
[9]Marceau V,No?l P A,Hébert-Dufresne L,Allard A,DubéL J 2010 Phys.Rev.E 82 036116
[10]Wu J,Tan Y J,Zheng H Z,Zhu D Z 2007 System Eng.Theor.Prac.27 101(in Chinese)[吴俊,谭跃进,郑宏钟,朱大智2007系统工程理论与实践27 101]
[11]SoléR V,Valverde S 2004 Lect.Notes Phys.650 189
[12]Cai M,Du H F,Ren Y K,Feldman M 2011 Acta Phys.Sin.60 110513(in Chinese)[蔡萌,杜海峰,任义科,费尔德曼M 2011物理学报60 110513]
[13]Yoon J,Blumer A,Lee K 2006 Bioinformatics 22 3106
[14]Zhang Q,Li M Z,Deng Y 2014 arXiv:1407.0097v1[cs.SI]
[15]Cai M,Du H F,Feldman M 2014 Acta Phys.Sin.63060504(in Chinese)[蔡萌,杜海峰,费尔德曼M 2014物理学报63 060504]
[16]Xiao L P,Meng H,Li D Y 2008 Geomatics Inf.Sci.Wuhan Univ.33 379(in Chinese)[肖俐平,孟晖,李德毅2008武汉大学学报(信息科学版)33 379]
[17]Gan W Y,He N,Li D Y,Wang J M 2009 J.Software20 2241(in Chinese)[淦文燕,赫南,李德毅,王建民2009软件学报20 2241]
[18]Watts D J,Strogatz S H 1998 Nature 393 440
[19]Humphries M D,Gurney K,Prescott T J 2006 Proc.R.Soc.B 273 503
[20]Humphries M D,Gurney K 2008 PLoS One 3 e0002051
[21]Barabási A L,Albert R 1999 Science 286 509
[22]Pan Z F,Wang X F 2006 Acta Phys.Sin.55 4508(in Chinese)[潘灶烽,汪小帆2006物理学报55 4508]
[23]Wang B H,Zhou T,Wang W X,Li J,Jiang P Q 2006Acta Phys.Sin.55 4051(in Chinese)[汪秉宏,周涛,王文旭,李季,蒋品群2006物理学报55 4051]
[24]Yang J M,Zhang N 2005 J.Univ.Shanghai Sci.Technol.27 413(in Chinese)[杨建民,张宁2005上海理工大学学报27 413]
[25]Holmgren?J 2006 Risk Anal.26 955
[26]Newman M E J 2003 SIAM Rev.45 167
[27]Chassin D P,Posse C 2005 Physica A 355 667
[2]Boccaletti S,Latora V,Moreno Y,Chavez M,Hwang DU 2006 Phys.Rep.424 175
[3]Vázquez A,Dobrin R,Sergi D,Eckmann J P,Oltvai ZN,Barabási A L 2004 Proc.Natl.Acad.Sci.USA 10117940
[4]Pinto P C,Thiran P,Vetterli M 2012 Phys.Rev.Lett.109 068702
[5]Yang Y Y,Xie G 2016 Inform.Process.Manage.52 911
[6]Newman M E J 2004 Eur.Phys.J.B 38 321
[7]Lermansinkoff D B,Barch D M 2016 Neuroimage-Clin.10 96
[8]Grabow C,Grosskinsky S,Timme M 2011 Eur.Phys.J.B 84 613
[9]Marceau V,No?l P A,Hébert-Dufresne L,Allard A,DubéL J 2010 Phys.Rev.E 82 036116
[10]Wu J,Tan Y J,Zheng H Z,Zhu D Z 2007 System Eng.Theor.Prac.27 101(in Chinese)[吴俊,谭跃进,郑宏钟,朱大智2007系统工程理论与实践27 101]
[11]SoléR V,Valverde S 2004 Lect.Notes Phys.650 189
[12]Cai M,Du H F,Ren Y K,Feldman M 2011 Acta Phys.Sin.60 110513(in Chinese)[蔡萌,杜海峰,任义科,费尔德曼M 2011物理学报60 110513]
[13]Yoon J,Blumer A,Lee K 2006 Bioinformatics 22 3106
[14]Zhang Q,Li M Z,Deng Y 2014 arXiv:1407.0097v1[cs.SI]
[15]Cai M,Du H F,Feldman M 2014 Acta Phys.Sin.63060504(in Chinese)[蔡萌,杜海峰,费尔德曼M 2014物理学报63 060504]
[16]Xiao L P,Meng H,Li D Y 2008 Geomatics Inf.Sci.Wuhan Univ.33 379(in Chinese)[肖俐平,孟晖,李德毅2008武汉大学学报(信息科学版)33 379]
[17]Gan W Y,He N,Li D Y,Wang J M 2009 J.Software20 2241(in Chinese)[淦文燕,赫南,李德毅,王建民2009软件学报20 2241]
[18]Watts D J,Strogatz S H 1998 Nature 393 440
[19]Humphries M D,Gurney K,Prescott T J 2006 Proc.R.Soc.B 273 503
[20]Humphries M D,Gurney K 2008 PLoS One 3 e0002051
[21]Barabási A L,Albert R 1999 Science 286 509
[22]Pan Z F,Wang X F 2006 Acta Phys.Sin.55 4508(in Chinese)[潘灶烽,汪小帆2006物理学报55 4508]
[23]Wang B H,Zhou T,Wang W X,Li J,Jiang P Q 2006Acta Phys.Sin.55 4051(in Chinese)[汪秉宏,周涛,王文旭,李季,蒋品群2006物理学报55 4051]
[24]Yang J M,Zhang N 2005 J.Univ.Shanghai Sci.Technol.27 413(in Chinese)[杨建民,张宁2005上海理工大学学报27 413]
[25]Holmgren?J 2006 Risk Anal.26 955
[26]Newman M E J 2003 SIAM Rev.45 167
[27]Chassin D P,Posse C 2005 Physica A 355 667