搜索

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

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

基于K-阶结构熵的网络异构性研究

黄丽亚 霍宥良 王青 成谢锋

引用本文:
Citation:

基于K-阶结构熵的网络异构性研究

黄丽亚, 霍宥良, 王青, 成谢锋

Network heterogeneity based on K-order structure entropy

Huang Li-Ya, Huo You-Liang, Wang Qing, Cheng Xie-Feng
PDF
导出引用
  • 结构熵可以考察复杂网络的异构性.为了弥补传统结构熵在综合刻画网络全局以及局部特性能力上的不足,本文依据网络节点在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.
    [1]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175

    [2]

    Vázquez A, Dobrin R, Sergi D, Eckmann J P, Oltvai Z N, Barabási A L 2004 Proc. Natl. Acad. Sci. USA 101 17940

    [3]

    Pinto P C, Thiran P, Vetterli M 2012 Phys. Rev. Lett. 109 068702

    [4]

    Yang Y Y, Xie G 2016 Inform. Process. Manage. 52 911

    [5]

    Newman M E J 2004 Eur. Phys. J. B 38 321

    [6]

    Lermansinkoff D B, Barch D M 2016 Neuroimage-Clin. 10 96

    [7]

    Grabow C, Grosskinsky S, Timme M 2011 Eur. Phys. J. B 84 613

    [8]

    Marceau V, Noël P A, Hébert-Dufresne L, Allard A, Dubé L J 2010 Phys. Rev. E 82 036116

    [9]

    Solé R V, Valverde S 2004 Lect. Notes Phys. 650 189

    [10]

    Yoon J, Blumer A, Lee K 2006 Bioinformatics 22 3106

    [11]

    Zhang Q, Li M Z, Deng Y 2014 arXiv:1407.0097v1 [cs. SI]

    [12]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [13]

    Humphries M D, Gurney K, Prescott T J 2006 Proc. R. Soc. B 273 503

    [14]

    Humphries M D, Gurney K 2008 PLoS One 3 e0002051

    [15]

    Barabási A L, Albert R 1999 Science 286 509

    [16]

    Holmgren Å J 2006 Risk Anal. 26 955

    [17]

    Newman M E J 2003 SIAM Rev. 45 167

    [18]

    Chassin D P, Posse C 2005 Physica A 355 667

  • [1]

    Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U 2006 Phys. Rep. 424 175

    [2]

    Vázquez A, Dobrin R, Sergi D, Eckmann J P, Oltvai Z N, Barabási A L 2004 Proc. Natl. Acad. Sci. USA 101 17940

    [3]

    Pinto P C, Thiran P, Vetterli M 2012 Phys. Rev. Lett. 109 068702

    [4]

    Yang Y Y, Xie G 2016 Inform. Process. Manage. 52 911

    [5]

    Newman M E J 2004 Eur. Phys. J. B 38 321

    [6]

    Lermansinkoff D B, Barch D M 2016 Neuroimage-Clin. 10 96

    [7]

    Grabow C, Grosskinsky S, Timme M 2011 Eur. Phys. J. B 84 613

    [8]

    Marceau V, Noël P A, Hébert-Dufresne L, Allard A, Dubé L J 2010 Phys. Rev. E 82 036116

    [9]

    Solé R V, Valverde S 2004 Lect. Notes Phys. 650 189

    [10]

    Yoon J, Blumer A, Lee K 2006 Bioinformatics 22 3106

    [11]

    Zhang Q, Li M Z, Deng Y 2014 arXiv:1407.0097v1 [cs. SI]

    [12]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [13]

    Humphries M D, Gurney K, Prescott T J 2006 Proc. R. Soc. B 273 503

    [14]

    Humphries M D, Gurney K 2008 PLoS One 3 e0002051

    [15]

    Barabási A L, Albert R 1999 Science 286 509

    [16]

    Holmgren Å J 2006 Risk Anal. 26 955

    [17]

    Newman M E J 2003 SIAM Rev. 45 167

    [18]

    Chassin D P, Posse C 2005 Physica A 355 667

计量
  • 文章访问数:  7472
  • PDF下载量:  156
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-07-19
  • 修回日期:  2018-11-08
  • 刊出日期:  2019-01-05

/

返回文章
返回