搜索

x

留言板

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

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

一种基于最大流的网络结构熵

蔡萌 杜海峰 费尔德曼

引用本文:
Citation:

一种基于最大流的网络结构熵

蔡萌, 杜海峰, 费尔德曼

A new network structure entropy based on maximum flow

Cai Meng, Du Hai-Feng, Marcus W Feldman
PDF
导出引用
  • 熵是可用来反映网络结构异质性的指标. 针对传统熵指标不能很好反映网络全局异构性的不足,本文引入网络流的概念,综合考虑径向测度和中间测度,提出一种新的网络结构熵. 特殊网络(如公用数据集Dolphins网络)的分析结果表明,本文提出的熵指标在一定程度上克服了其他网络熵指标的不足,更能够反映网络的真实拓扑结构;对随机网络、最近邻耦合网络、星型网络、无标度网络、Benchmark网络和小世界网络等典型网络的理论分析和仿真实验,进一步证明本文提出的熵指标在刻画一般复杂网络结构特征上的有效性和适用性.
    Entropy is an index to reflect the heterogeneity of network structure. By introducing the concept of network flow which comprehensively considers radial measurement and betweenness measurement, we define a new network structure entropy index to solve the problem that classical entropy indices cannot effectively reflect heterogeneity of the global network. Analysis results concerning specific network (e.g. public data set Dolphins network) indicate that this new entropy index can reflect the real topological structure of network, and effectively overcome the shortcomings of other network entropy indices to some extent. The theoretical analyses and simulation experiments on Erdös-Renyi random network, nearest-neighbor coupled network, star network, Barabási-Albert scale-free network, Benchmark network, and the Watts-Strogatz small-world network further prove the effectiveness and applicability of this new network structure entropy index to describe the characteristics of ordinary complex network structures.
    • 基金项目: 国家社会科学基金重点项目(批准号:12AZD110)、国家自然科学基金(批准号:71071128)、国家教育部新世纪优秀人才支持计划(批准号:NCET-08-0451)和中央高校基本科研业务费专项资金(批准号:2011jdgz08)资助的课题.
    • Funds: Project supported by the National Social Science Foundation of China (Grant No. 12AZD110), the National Natural Science Foundation of China (Grant No. 71071128), the Program for New Century Excellent Talents in University of Ministry of Education of China (Grant No. NCET-08-0451) and the Fundamental Research Funds for the Central Universities, China (Grant No. 2011jdgz08).
    [1]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [2]

    Wang H, Han J H, Deng L, Cheng K Q 2013 Acta Phys. Sin. 62 110505 (in Chinese) [王辉, 韩江洪, 邓林, 程克勤 2013 物理学报 62 110505]

    [3]

    Li R Q, Tang M, Hui P M 2013 Acta Phys. Sin. 62 168903 (in Chinese) [李睿琪, 唐明, 许伯铭 2013 物理学报 62 168903]

    [4]

    Huang B, Zhao X Y, Qi K, Tang M, Du Y H 2013 Acta Phys. Sin. 62 218902 (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218902]

    [5]

    Weng W G, Ni S J, Shen S F, Yuan H Y 2007 Acta Phys. Sin. 56 1938 (in Chinese) [翁文国, 倪顺江, 申世飞, 袁宏永 2007 物理学报 56 1938]

    [6]

    Ou Y M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 (in Chinese) [欧阳敏, 费奇, 余明晖 2008 物理学报 57 6763]

    [7]

    Song Y R, Jiang G P 2010 Acta Phys. Sin. 59 7546 (in Chinese) [宋玉蓉, 蒋国平 2010 物理学报 59 7546]

    [8]

    Wang Y Q, Yang X Y 2013 Chin. Phys. B 22 010509

    [9]

    Song Y R, Jiang G P, Gong Y W 2013 Chin. Phys. B 22 040205

    [10]

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

    [11]

    Costa L F, Rodrigues F A, Travieso G, Boas P R V 2007 Adv. Phys. 56 167

    [12]

    Wu J, Tan Y J, Deng H Z, Zhu D Z 2007 Systems Engineer Theory & Practice 27 101 (in Chinese) [吴俊, 谭跃进, 郑宏钟, 朱大智 2007 系统工程理论与实践 27 101]

    [13]

    Wang B, Tang H W, Guo C H, Xiu Z L 2006 Physica A 363 591

    [14]

    Cai M, Du H F, Ren Y K, Feldman M 2011 Acta Phys. Sin. 60 110513 (in Chinese) [蔡萌, 杜海峰, 任义科, 费尔德曼 2011 物理学报 60 110513]

    [15]

    Freeman L C, Borgatti S P, White D R 1991 Social Networks 13 141

    [16]

    Winston W L 1994 Operations Research: Applications and Algorithms (Belmont: Duxbury Press) p15

    [17]

    Borgatti S P, Everett M G 2006 Social Networks 28 466

    [18]

    Putnam R D 2000 Bowling Alone: The Collapse and Revival of American Community (New York: Simon & Schuster) p65

    [19]

    Freeman L C 1980 Quality and Quantity 14 585

    [20]

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Application (Vol. 1) (Beijing: Tsinghua University Press) p18 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第18页]

    [21]

    Erods P, Renyi A 1960 Publ. Math. Inst. Hungary Acd. Sci. 5 17

    [22]

    Barabasi A L, Albert R 1999 Science 286 509

    [23]

    Girvan M, Newman M E J 2002 PNAS 99 7821

    [24]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [26]

    Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396

    [27]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

  • [1]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [2]

    Wang H, Han J H, Deng L, Cheng K Q 2013 Acta Phys. Sin. 62 110505 (in Chinese) [王辉, 韩江洪, 邓林, 程克勤 2013 物理学报 62 110505]

    [3]

    Li R Q, Tang M, Hui P M 2013 Acta Phys. Sin. 62 168903 (in Chinese) [李睿琪, 唐明, 许伯铭 2013 物理学报 62 168903]

    [4]

    Huang B, Zhao X Y, Qi K, Tang M, Du Y H 2013 Acta Phys. Sin. 62 218902 (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218902]

    [5]

    Weng W G, Ni S J, Shen S F, Yuan H Y 2007 Acta Phys. Sin. 56 1938 (in Chinese) [翁文国, 倪顺江, 申世飞, 袁宏永 2007 物理学报 56 1938]

    [6]

    Ou Y M, Fei Q, Yu M H 2008 Acta Phys. Sin. 57 6763 (in Chinese) [欧阳敏, 费奇, 余明晖 2008 物理学报 57 6763]

    [7]

    Song Y R, Jiang G P 2010 Acta Phys. Sin. 59 7546 (in Chinese) [宋玉蓉, 蒋国平 2010 物理学报 59 7546]

    [8]

    Wang Y Q, Yang X Y 2013 Chin. Phys. B 22 010509

    [9]

    Song Y R, Jiang G P, Gong Y W 2013 Chin. Phys. B 22 040205

    [10]

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

    [11]

    Costa L F, Rodrigues F A, Travieso G, Boas P R V 2007 Adv. Phys. 56 167

    [12]

    Wu J, Tan Y J, Deng H Z, Zhu D Z 2007 Systems Engineer Theory & Practice 27 101 (in Chinese) [吴俊, 谭跃进, 郑宏钟, 朱大智 2007 系统工程理论与实践 27 101]

    [13]

    Wang B, Tang H W, Guo C H, Xiu Z L 2006 Physica A 363 591

    [14]

    Cai M, Du H F, Ren Y K, Feldman M 2011 Acta Phys. Sin. 60 110513 (in Chinese) [蔡萌, 杜海峰, 任义科, 费尔德曼 2011 物理学报 60 110513]

    [15]

    Freeman L C, Borgatti S P, White D R 1991 Social Networks 13 141

    [16]

    Winston W L 1994 Operations Research: Applications and Algorithms (Belmont: Duxbury Press) p15

    [17]

    Borgatti S P, Everett M G 2006 Social Networks 28 466

    [18]

    Putnam R D 2000 Bowling Alone: The Collapse and Revival of American Community (New York: Simon & Schuster) p65

    [19]

    Freeman L C 1980 Quality and Quantity 14 585

    [20]

    Wang X F, Li X, Chen G R 2006 Complex Network Theory and Application (Vol. 1) (Beijing: Tsinghua University Press) p18 (in Chinese) [汪小帆, 李翔, 陈关荣 2006 复杂网络理论及其应用 (北京: 清华大学出版社) 第18页]

    [21]

    Erods P, Renyi A 1960 Publ. Math. Inst. Hungary Acd. Sci. 5 17

    [22]

    Barabasi A L, Albert R 1999 Science 286 509

    [23]

    Girvan M, Newman M E J 2002 PNAS 99 7821

    [24]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

    [25]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [26]

    Lusseau D, Schneider K, Boisseau O J, Haase P, Slooten E, Dawson S M 2003 Behav. Ecol. Sociobiol. 54 396

    [27]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

  • [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] 黄丽亚, 霍宥良, 王青, 成谢锋. 基于K-阶结构熵的网络异构性研究. 物理学报, 2019, 68(1): 018901. doi: 10.7498/aps.68.20181388
    [7] 孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [8] 徐明, 许传云, 曹克非. 度相关性对无向网络可控性的影响. 物理学报, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [9] 李勇军, 尹超, 于会, 刘尊. 基于最大熵模型的微博传播网络中的链路预测. 物理学报, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
    [10] 侯绿林, 老松杨, 肖延东, 白亮. 复杂网络可控性研究现状综述. 物理学报, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [11] 黄飞虎, 彭舰, 宁黎苗. 基于信息熵的社交网络观点演化模型. 物理学报, 2014, 63(16): 160501. doi: 10.7498/aps.63.160501
    [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
计量
  • 文章访问数:  7289
  • PDF下载量:  1140
  • 被引次数: 0
出版历程
  • 收稿日期:  2013-10-08
  • 修回日期:  2013-11-20
  • 刊出日期:  2014-03-05

/

返回文章
返回