Caveman网络及其在复杂网络熵分析中的应用

蔡萌, 杜海峰, 费尔德曼

系统工程理论与实践 ›› 2017, Vol. 37 ›› Issue (9) : 2403-2412.

PDF(1356 KB)
PDF(1356 KB)
系统工程理论与实践 ›› 2017, Vol. 37 ›› Issue (9) : 2403-2412. DOI: 10.12011/1000-6788(2017)09-2403-10
论文

Caveman网络及其在复杂网络熵分析中的应用

    蔡萌1, 杜海峰2, 费尔德曼2,3
作者信息 +

Caveman network and its application in analysis of complex network entropy

    CAI Meng1, DU Haifeng2, MARCUS W. Feldman2,3
Author information +
文章历史 +

摘要

熵可以有效反映复杂系统内网络结构的异质性.针对熵指标在刻画网络全局异构上是否适用这一问题,目前仍缺少用以评测的基准网络.对此,在已有结构熵研究的基础上,提出一种Caveman网络构造及其演化规则,为网络复杂性的度量提供新的思路.通过数理分析和仿真实验验证该Caveman网络可以有效评测各类结构熵指标对其演化过程的敏感性,反映熵指标对网络复杂特征识别能力的差异.同时由于Caveman网络可以更好地探索信息空间和抵御攻击,将有助于设计鲁棒、高效的系统结构.

Abstract

Entropy can effectively reflect the network structure heterogeneity of complex systems. For the question of applicability of entropy indices to describe the global heterogeneity of the network, the benchmark networks for the evaluation are still lacking. On the foundation of previous study, this paper introduces a Caveman network and its evolution rules, which provides a new way of thinking for measurement of network complexity. The theoretical analysis and simulation experiments indicate that the Caveman network can effectively evaluate the sensitivity of different structure entropies on evolution process of Caveman network, and reflect the difference of ability to identify the properties of network complex of entropy indices. Besides that, Caveman network can promote exploration in information space and resist network attacks, shedding new light on designing system structure with high robustness and efficiency.

关键词

复杂系统 / Caveman网络 / 异质性 /

Key words

complex system / Caveman network / heterogeneity / entropy

引用本文

导出引用
蔡萌 , 杜海峰 , 费尔德曼. Caveman网络及其在复杂网络熵分析中的应用. 系统工程理论与实践, 2017, 37(9): 2403-2412 https://doi.org/10.12011/1000-6788(2017)09-2403-10
CAI Meng , DU Haifeng , MARCUS W. Feldman. Caveman network and its application in analysis of complex network entropy. Systems Engineering - Theory & Practice, 2017, 37(9): 2403-2412 https://doi.org/10.12011/1000-6788(2017)09-2403-10
中图分类号: N945   

参考文献

[1] 马剑, 许素梅, 范文博, 等. 大规模人群网络流瓶颈识别方法研究[J]. 系统工程理论与实践, 2016, 36(1):164-173.Ma J, Xu S M, Fan W B, et al. Method of bottleneck identification for massive crowd circulating network[J]. Systems Engineering-Theory & Practice, 2016, 36(1):164-173.
[2] Sandhu R, Georgiou T, Reznik E, et al. Graph curvature for differentiating cancer networks[J]. Scientific Reports, 2015(5):12323(1-13).
[3] Hinrichsen H, HoBfeld T, Hirth M, et al. Entropy production in stationary social networks[J]. Complex Networks IV:Studies in Computational Intelligence, 2013, 476:47-58.
[4] Tutzauer F. Entropy as a measure of centrality in networks characterized by path-transfer flow[J]. Social Networks, 2007, 29(2):249-265.
[5] Li J, Wang B H, Wang W X, et al. Network entropy based on topology configuration and its computation to random networks[J]. Chinese Physics Letters, 2008, 25(11):4177-4180.
[6] 吴俊, 谭跃进, 郑宏钟, 等. 无标度网络拓扑结构非均匀性研究[J]. 系统工程理论与实践, 2007, 27(5):101-105.Wu J, Tan Y J, Deng H Z, et al. Heterogeneity of scale-free network topology[J]. Systems Engineering-Theory & Practice, 2007, 27(5):101-105.
[7] Solé R V, Valverde S. Information theory of complex networks:On evolution and architectural constraints[M]//Complex Networks, 2004, 650:189-207.
[8] 蔡萌, 杜海峰, 任义科, 等. 一种基于点和边差异性的网络结构熵[J]. 物理学报, 2011, 60(11):110513(1-9). Cai M, Du H F, Ren Y K, et al. A new network structure entropy based node difference and edge difference[J]. Acta Physica Sinica, 2011, 60(11):110513(1-9).
[9] Romualdo P S, Claudio C, Piet V M, et al. Epidemic processes in complex networks[J]. Reviews of Modern Physics, 2015, 87(3):925-979.
[10] 蔡萌, 杜海峰, 费尔德曼. 一种基于最大流的网络结构熵[J]. 物理学报, 2014, 63(6):060504(1-11).Cai M, Du H F, Feldman M W. A new network structure entropy based on maximum flow[J]. Acta Physica Sinica, 2014, 63(6):060504(1-11).
[11] Zhao C, Wang W X, Liu Y Y, et al. Intrinsic dynamics induce global symmetry in network controllability[J]. Scientific Reports, 2015(5):8422(1-5).
[12] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439):509-512.
[13] Watts D J, Strogatz S H. Collective dynamics of‘small-world’networks[J]. Nature, 1998, 393(6684):440-442.
[14] Watts D J. Small worlds:The dynamics of networks between order and randomness[M]. Princeton, NJ:Princeton University Press, 1999.
[15] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99:7821-7826.
[16] Vicente R S, Adelgcio B F, Rafaela R A. Shannon information entropy for assessing space-time variability of rainfall and streamflow in semiarid region[J]. Science of the Total Environment, 2016, 544:330-338.
[17] Rashevsky N. Life information theory and topology[J]. Bulletin of Mathematical Biophysics, 1955, 17:229-235.
[18] Trucco E. A note on the information content of graphs[J]. Bulletin of Mathematical Biology, 1956, 18(2):129-135.
[19] Borgatti S P, Everett M G. A graph-theoretic perspective on centrality[J]. Social Networks, 2006, 28:466-484.
[20] Yu Y, Xiao G, Zhou J, et al. System crash as dynamics of complex networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2016, 113(42):11726-11731.
[21] Shore J, Bernstein E, Lazer D. Facts and figuring:An experimental investigation of network structure and performance in information and solution spaces[J]. Organization Science, 2015, 26(5):1432-1446.
[22] 杜巍, 蔡萌, 杜海峰. 网络结构鲁棒性指标及应用研究[J].西安交通大学学报, 2010, 44(4):93-97. Du W, Cai M, Du H F. Study on indices of network structure robustness and their application[J]. Journal of Xi'an Jiaotong University, 2010, 44(4):93-97.
[23] 郑小京, 郑君君. 个体规则驱动的群体行为对称性破缺的临界状态[J]. 系统工程理论与实践, 2016, 36(2):413-426. Zheng X J, Zheng J J. Criticality of symmetry breaking of collective behavior driven by individual rules[J]. Systems Engineering-Theory & Practice, 2016, 36(2):413-426.

基金

国家自然科学基金(71501153);国家社会科学基金重点项目(12AZD110);陕西省软科学研究计划(2015KRM051);中央高校基本科研业务费专项资金(JB150602)
PDF(1356 KB)

Accesses

Citation

Detail

段落导航
相关文章

/