A new network structure entropy based on maximum flow

Cai Meng; Du Hai-Feng; Marcus W Feldman

doi:10.7498/aps.63.060504

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:

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).

References

[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]

Cited By

[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]	Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[2]	Zhao Guo-Tao, Wang Li-Fu, Guan Bo-Fei. A class of edge set affecting network controllability. Acta Physica Sinica, 2021, 70(14): 148902. doi: 10.7498/aps.70.20201831
[3]	Ma Jin-Long, Zhang Jun-Feng, Zhang Dong-Wen, Zhang Hong-Bin. Quantifying complex network traffic capacity based on communicability sequence entropy. Acta Physica Sinica, 2021, 70(7): 078902. doi: 10.7498/aps.70.20201300
[4]	Tan Suo-Yi, Qi Ming-Ze, Wu Jun, Lu Xin. Link predictability of complex network from spectrum perspective. Acta Physica Sinica, 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817
[5]	Chen Dan, Shi Dan-Dan, Pan Gui-Jun. Correlation between the electrical transport performance and the communicability sequence entropy in complex networks. Acta Physica Sinica, 2019, 68(11): 118901. doi: 10.7498/aps.68.20190230
[6]	Huang Li-Ya, Huo You-Liang, Wang Qing, Cheng Xie-Feng. Network heterogeneity based on K-order structure entropy. Acta Physica Sinica, 2019, 68(1): 018901. doi: 10.7498/aps.68.20181388
[7]	Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[8]	Xu Ming, Xu Chuan-Yun, Cao Ke-Fei. Effect of degree correlations on controllability of undirected networks. Acta Physica Sinica, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
[9]	Li Yong-Jun, Yin Chao, Yu Hui, Liu Zun. Link prediction in microblog retweet network based on maximum entropy model. Acta Physica Sinica, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
[10]	Hou Lü-Lin, Lao Song-Yang, Xiao Yan-Dong, Bai Liang. Recent progress in controllability of complex network. Acta Physica Sinica, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
[11]	Huang Fei-Hu, Peng Jian, Ning Li-Miao. Opinion evolution model of social network based on information entropy. Acta Physica Sinica, 2014, 63(16): 160501. doi: 10.7498/aps.63.160501
[12]	Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[13]	Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
[14]	Gao Xiang-Yun, An Hai-Zhong, Fang Wei. Research on fluctuation of bivariate correlation of time series based on complex networks theory. Acta Physica Sinica, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
[15]	Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[16]	Cai Meng, Du Hai-Feng, Ren Yi-Ke, Marcus W. A new network structure entropy based node difference and edge difference. Acta Physica Sinica, 2011, 60(11): 110513. doi: 10.7498/aps.60.110513
[17]	Liu Xiao-Feng, Yu Wen-Li. A symbolic dynamics approach to the complexity analysis of event-related potentials. Acta Physica Sinica, 2008, 57(4): 2587-2594. doi: 10.7498/aps.57.2587
[18]	Guo Jin-Li. Impact of edges for new nodes on scale-free networks. Acta Physica Sinica, 2008, 57(2): 756-761. doi: 10.7498/aps.57.756
[19]	Xiao Fang-Hong, Yan Gui-Rong, Han Yu-Hang. A symbolic dynamics approach for the complexity analysis of chaotic pseudo-random sequences. Acta Physica Sinica, 2004, 53(9): 2876-2881. doi: 10.7498/aps.53.2876
[20]	Song Tai-Peng, Hou Chen-Xia, Shi Wang-Lin. . Acta Physica Sinica, 2002, 51(6): 1398-1402. doi: 10.7498/aps.51.1398

Catalog

Vol. 63, Issue 6 - 2014-03-20

Metrics

Abstract views: 8066
PDF Downloads: 1141
Cited By: 0

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

Search

Article

留言板