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

蔡萌; 杜海峰; 费尔德曼

doi:10.7498/aps.63.060504

摘要

熵是可用来反映网络结构异质性的指标. 针对传统熵指标不能很好反映网络全局异构性的不足，本文引入网络流的概念，综合考虑径向测度和中间测度，提出一种新的网络结构熵. 特殊网络（如公用数据集Dolphins网络）的分析结果表明，本文提出的熵指标在一定程度上克服了其他网络熵指标的不足，更能够反映网络的真实拓扑结构；对随机网络、最近邻耦合网络、星型网络、无标度网络、Benchmark网络和小世界网络等典型网络的理论分析和仿真实验，进一步证明本文提出的熵指标在刻画一般复杂网络结构特征上的有效性和适用性.

关键词:

复杂网络 /
异构性 /
熵

Abstract

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.

Keywords:

作者及机构信息

1.
西安交通大学管理学院, 西安 710049;

2.
西安交通大学公共管理与复杂性科学研究中心, 西安 710049;

3.
斯坦福大学莫里森人口与资源研究所, 斯坦福 94305

基金项目: 国家社会科学基金重点项目（批准号：12AZD110）、国家自然科学基金（批准号：71071128）、国家教育部新世纪优秀人才支持计划（批准号：NCET-08-0451）和中央高校基本科研业务费专项资金（批准号：2011jdgz08）资助的课题.

Authors and contacts

1.
School of Management, Xi’an Jiaotong University, Xi’an 710049, China;

2.
Center for Administration and Complexity Science, Xi’an Jiaotong University, Xi’an 710049, China;

3.
Morrison Institute for Population and Resource Studies, Stanford University, Stanford 94305, USA

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

计量

文章访问数: 8089
PDF下载量: 1141
被引次数: 0

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

搜索

留言板