搜索

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

  • [1] 汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [2] 赵国涛, 王立夫, 关博飞. 一类影响网络能控性的边集研究. 物理学报, 2021, 70(14): 148902. doi: 10.7498/aps.70.20201831
    [3] 马金龙, 张俊峰, 张冬雯, 张红斌. 基于通信序列熵的复杂网络传输容量. 物理学报, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
    [4] 谭索怡, 祁明泽, 吴俊, 吕欣. 复杂网络链路可预测性: 基于特征谱视角. 物理学报, 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817
    [5] 陈单, 石丹丹, 潘贵军. 复杂网络电输运性能与通信序列熵之间的关联. 物理学报, 2019, 68(11): 118901. doi: 10.7498/aps.68.20190230
    [6] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [7] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [8] 李勇军, 尹超, 于会, 刘尊. 基于最大熵模型的微博传播网络中的链路预测. 物理学报, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
    [9] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [10] 黄飞虎, 彭舰, 宁黎苗. 基于信息熵的社交网络观点演化模型. 物理学报, 2014, 63(16): 160501. doi: 10.7498/aps.63.160501
    [11] 蔡萌, 杜海峰, 费尔德曼. 一种基于最大流的网络结构熵. 物理学报, 2014, 63(6): 060504. doi: 10.7498/aps.63.060504
    [12] 刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [13] 于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [14] 高湘昀, 安海忠, 方伟. 基于复杂网络的时间序列双变量相关性波动研究. 物理学报, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [15] 周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. 物理学报, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [16] 蔡萌, 杜海峰, 任义科, 费尔德曼. 一种基于点和边差异性的网络结构熵. 物理学报, 2011, 60(11): 110513. doi: 10.7498/aps.60.110513
    [17] 刘小峰, 俞文莉. 基于符号动力学的认知事件相关电位的复杂度分析. 物理学报, 2008, 57(4): 2587-2594. doi: 10.7498/aps.57.2587
    [18] 郭进利. 新节点的边对网络无标度性影响. 物理学报, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
    [19] 肖方红, 阎桂荣, 韩宇航. 混沌伪随机序列复杂度分析的符号动力学方法. 物理学报, 2004, 53(9): 2876-2881. doi: 10.7498/aps.53.2876
    [20] 宋太平, 侯晨霞, 史旺林. Vaidya-Bonner黑洞的熵. 物理学报, 2002, 51(6): 1398-1402. doi: 10.7498/aps.51.1398
计量
  • 文章访问数:  7927
  • PDF下载量:  163
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-07-19
  • 修回日期:  2018-11-08
  • 刊出日期:  2019-01-05

/

返回文章
返回