Search

Article

x

留言板

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

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

Effect of degree correlations on controllability of undirected networks

Xu Ming Xu Chuan-Yun Cao Ke-Fei

Effect of degree correlations on controllability of undirected networks

Xu Ming, Xu Chuan-Yun, Cao Ke-Fei
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • The controllability analysis of complex networks is of great importance for modern network science and engineering. Existing research shows that the controllability of a complex network is affected not only by the degree distribution of the network,but also by the degree correlation.Although the effect of degree correlations on the network controllability is well studied for directed networks,it is not yet very clear for the case of undirected networks.To explore the impact of degree correlations on the controllability of undirected networks and their corresponding generalized (bidirectional and directed) networks,in this paper,we use the simulated annealing algorithm to change the network degree correlation coefficients by link rewiring.First,the undirected Erdős-Rényi random network and the modified scale-free network are taken as example models to be investigated.Numerical simulations show that the controllability measure (density of driver nodes) of undirected networks decreases monotonically with the increase of the degree correlation coefficient under a constant degree distribution.Specifically,when the degree correlation coefficient changes from -1 to 0,the controllability measure decreases rapidly;while the decrease in the controllability measure is not obvious when the degree correlation coefficient changes from 0 to 1.Next,the bidirectional networks and some directed networks are considered;in these networks,the in-degree of each node is equal to its out-degree,thus link rewiring results in the simultaneous changes of various degree correlations (i.e.,in-in,in-out,out-in,and out-out degree correlations).Further investigations show that these bidirectional and directed networks also follow the above rule,which is verified by the two real networks.The increase of the degree correlation coefficient in undirected networks also implies the increases of various degree correlation coefficients in the corresponding directed networks.Although the effect of a single degree correlation on the controllability of directed networks is clear,the comprehensive effect of the simultaneous changes in various degree correlations on the network controllability cannot be additively and therefore directly estimated by the relevant results in the corresponding directed networks;namely,the effect of the degree correlation on the controllability in an undirected network has its special rule.Some explanations are given for this phenomenon.Moreover,for a large sparse network without self-loops,no matter how assortative or disassortative it is,its structural controllability and exact controllability are verified to be almost the same.These studies will deepen the understanding of the relationship between the network controllability and the network structure.
      Corresponding author: Cao Ke-Fei, kfcao163@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 11365023), the Joint Fund of Department of Science and Technology of Guizhou Province/Bureau of Science and Technology of Qiandongnan Prefecture/Kaili University, China (Grant No. LH-2014-7231), and the Science and Technology Talent Support Program of Department of Education of Guizhou Province, China (Grant No. KY-2015-505).
    [1]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [2]

    Pósfai M, Liu Y Y, Slotine J J, Barabási A L 2014 J. Univ. Electron. Sci. Technol. China 43 1 (in Chinese)[周涛, 张子柯, 陈关荣, 汪小帆, 史定华, 狄增如, 樊瑛, 方锦清, 韩筱璞, 刘建国, 刘润然, 刘宗华, 陆君安, 吕金虎, 吕琳媛, 荣智海, 汪秉宏, 许小可, 章忠志2014电子科技大学学报43 1]

    [3]

    Ruths J, Ruths D 2014 Science 343 1373

    [4]

    Wuchty S 2014 Proc. Natl. Acad. Sci. U.S.A. 111 7156

    [5]

    Xu M, Xu C Y, Wang H, Deng C Z, Cao K F 2015 Eur. Phys. J. B 88 168

    [6]

    Xu C J, Zheng Y, Su H S, Wang H O 2015 Int. J. Control 88 248

    [7]

    Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901 (in Chinese)[侯绿林, 老松杨, 肖延东, 白亮2015物理学报64 188901]

    [8]

    Nie S, Wang X W, Wang B H 2015 Physica A 436 98

    [9]

    Ruths D, Ruths J 2016 Sci. Rep. 6 19818

    [10]

    Kawakami E, Singh V K, Matsubara K, Ishii T, Matsuoka Y, Hase T, Kulkarni P, Siddiqui K, Kodilkar J, Danve N, Subramanian I, Katoh M, Shimizu-Yoshida Y, Ghosh S, Jere A, Kitano H 2016 NPJ Syst. Biol. Appl. 2 15018

    [11]

    Kalman R E 1963 J. Soc. Ind. Appl. Math. Ser. A 1 152

    [12]

    Lombardi A, Härnquist M 2007 Phys. Rev. E 75 056110

    [13]

    Lin C T 1974 IEEE Trans. Autom. Contr. 19 201

    [14]

    Lovász L, Plummer M D 1986 Matching Theory (Amsterdam:North-Holland) pp83-119

    [15]

    Mézard M, Parisi G 2001 Eur. Phys. J. B 20 217

    [16]

    Hautus M L J 1969 Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen Ser. A 72 443

    [17]

    Wang X F, Chen G R 2002 Physica A 310 521

    [18]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [19]

    Zhou M Y, He X S, Fu Z Q, Liao H, Cai S M, Zhuo Z 2016 Physica A 446 120

    [20]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [21]

    Newman M E J 2002 Phys. Rev. Lett. 89 208701

    [22]

    Foster J G, Foster D V, Grassberger P, Paczuski M 2010 Proc. Natl. Acad. Sci. U.S.A. 107 10815

    [23]

    Newman M E J 2003 Phys. Rev. E 67 026126

    [24]

    Maslov S, Sneppen K 2002 Science 296 910

    [25]

    Hopcroft J E, Karp R M 1973 SIAM J. Comput. 2 225

    [26]

    Qu J, Wang S J 2015 Acta Phys. Sin. 64 198901 (in Chinese)[屈静, 王圣军2015物理学报64 198901]

    [27]

    Goh K I, Kahng B, Kim D 2001 Phys. Rev. Lett. 87 278701

    [28]

    Kirkpatrick S, Gelatt Jr C D, Vecchi M P 1983 Science 220 671

    [29]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [30]

    Watts D J, Strogatz S H 1998 Nature 393 440

  • [1]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [2]

    Pósfai M, Liu Y Y, Slotine J J, Barabási A L 2014 J. Univ. Electron. Sci. Technol. China 43 1 (in Chinese)[周涛, 张子柯, 陈关荣, 汪小帆, 史定华, 狄增如, 樊瑛, 方锦清, 韩筱璞, 刘建国, 刘润然, 刘宗华, 陆君安, 吕金虎, 吕琳媛, 荣智海, 汪秉宏, 许小可, 章忠志2014电子科技大学学报43 1]

    [3]

    Ruths J, Ruths D 2014 Science 343 1373

    [4]

    Wuchty S 2014 Proc. Natl. Acad. Sci. U.S.A. 111 7156

    [5]

    Xu M, Xu C Y, Wang H, Deng C Z, Cao K F 2015 Eur. Phys. J. B 88 168

    [6]

    Xu C J, Zheng Y, Su H S, Wang H O 2015 Int. J. Control 88 248

    [7]

    Hou L L, Lao S Y, Xiao Y D, Bai L 2015 Acta Phys. Sin. 64 188901 (in Chinese)[侯绿林, 老松杨, 肖延东, 白亮2015物理学报64 188901]

    [8]

    Nie S, Wang X W, Wang B H 2015 Physica A 436 98

    [9]

    Ruths D, Ruths J 2016 Sci. Rep. 6 19818

    [10]

    Kawakami E, Singh V K, Matsubara K, Ishii T, Matsuoka Y, Hase T, Kulkarni P, Siddiqui K, Kodilkar J, Danve N, Subramanian I, Katoh M, Shimizu-Yoshida Y, Ghosh S, Jere A, Kitano H 2016 NPJ Syst. Biol. Appl. 2 15018

    [11]

    Kalman R E 1963 J. Soc. Ind. Appl. Math. Ser. A 1 152

    [12]

    Lombardi A, Härnquist M 2007 Phys. Rev. E 75 056110

    [13]

    Lin C T 1974 IEEE Trans. Autom. Contr. 19 201

    [14]

    Lovász L, Plummer M D 1986 Matching Theory (Amsterdam:North-Holland) pp83-119

    [15]

    Mézard M, Parisi G 2001 Eur. Phys. J. B 20 217

    [16]

    Hautus M L J 1969 Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen Ser. A 72 443

    [17]

    Wang X F, Chen G R 2002 Physica A 310 521

    [18]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [19]

    Zhou M Y, He X S, Fu Z Q, Liao H, Cai S M, Zhuo Z 2016 Physica A 446 120

    [20]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [21]

    Newman M E J 2002 Phys. Rev. Lett. 89 208701

    [22]

    Foster J G, Foster D V, Grassberger P, Paczuski M 2010 Proc. Natl. Acad. Sci. U.S.A. 107 10815

    [23]

    Newman M E J 2003 Phys. Rev. E 67 026126

    [24]

    Maslov S, Sneppen K 2002 Science 296 910

    [25]

    Hopcroft J E, Karp R M 1973 SIAM J. Comput. 2 225

    [26]

    Qu J, Wang S J 2015 Acta Phys. Sin. 64 198901 (in Chinese)[屈静, 王圣军2015物理学报64 198901]

    [27]

    Goh K I, Kahng B, Kim D 2001 Phys. Rev. Lett. 87 278701

    [28]

    Kirkpatrick S, Gelatt Jr C D, Vecchi M P 1983 Science 220 671

    [29]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [30]

    Watts D J, Strogatz S H 1998 Nature 393 440

  • [1] 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
    [2] 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
    [3] 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
    [4] 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
    [5] 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
    [6] 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
    [7] Tan Suo-Yi, Qi Ming-Ze, Wu Jun, Lu Xin. The link predictability of complex network from a spectrum perspective. Acta Physica Sinica, 2020, 69(8): 1-10. doi: 10.7498/aps.69.20191817
    [8] Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [9] 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
    [10] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [11] Gong Zhi-Qiang, Zhi Rong, Hou Wei, Wang Xiao-Juan, Feng Guo-Ling. Analysis of decadal characteristics of leading teleconnections based on complex networks theory. Acta Physica Sinica, 2012, 61(2): 029202. doi: 10.7498/aps.61.029202
    [12] Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun. Multi-resolution density modularity for finding community structure in complex networks. Acta Physica Sinica, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [13] 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
    [14] Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya. Evaluating influential spreaders in complex networks by extension of degree. Acta Physica Sinica, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [15] Yu Xiao-Ping, Pei Tao. Analysis on degree characteristics of mobile call network. Acta Physica Sinica, 2013, 62(20): 208901. doi: 10.7498/aps.62.208901
    [16] Hu Yao-Guang, Wang Sheng-Jun, Jin Tao, Qu Shi-Xian. Biased random walks in the scale-free networks with the disassortative degree correlation. Acta Physica Sinica, 2015, 64(2): 028901. doi: 10.7498/aps.64.028901
    [17] Yan Xiao-Yong, Wang Ming-Sheng. Influence of growth speed on the actors’ degree distribution of collaboration networks. Acta Physica Sinica, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851
    [18] Yuan Chao, Chai Yi. Group similarity based algorithm for network community structure detection. Acta Physica Sinica, 2012, 61(21): 218901. doi: 10.7498/aps.61.218901
    [19] Duan Dong-Li, Zhan Ren-Jun. Evolution mechanism of node importance based on the information about cascading failures in complex networks. Acta Physica Sinica, 2014, 63(6): 068902. doi: 10.7498/aps.63.068902
    [20] Hou Feng-Zhen, Dai Jia-Fei, Liu Xin-Feng, Huang Xiao-Lin. Phase synchrony in the cerebral infarction electroencephalogram based on the degree of network-links. Acta Physica Sinica, 2014, 63(4): 040506. doi: 10.7498/aps.63.040506
  • Citation:
Metrics
  • Abstract views:  602
  • PDF Downloads:  401
  • Cited By: 0
Publishing process
  • Received Date:  23 July 2016
  • Accepted Date:  05 September 2016
  • Published Online:  20 January 2017

Effect of degree correlations on controllability of undirected networks

    Corresponding author: Cao Ke-Fei, kfcao163@163.com
  • 1. Center for Nonlinear Complex Systems, School of Physics and Astronomy, Yunnan University, Kunming 650091, China;
  • 2. School of Mathematical Sciences, Kaili University, Kaili 556011, China;
  • 3. School of Mathematics and Statistics, Guizhou University of Finance and Economics, Guiyang 550025, China
Fund Project:  Project supported by the National Natural Science Foundation of China (Grant No. 11365023), the Joint Fund of Department of Science and Technology of Guizhou Province/Bureau of Science and Technology of Qiandongnan Prefecture/Kaili University, China (Grant No. LH-2014-7231), and the Science and Technology Talent Support Program of Department of Education of Guizhou Province, China (Grant No. KY-2015-505).

Abstract: The controllability analysis of complex networks is of great importance for modern network science and engineering. Existing research shows that the controllability of a complex network is affected not only by the degree distribution of the network,but also by the degree correlation.Although the effect of degree correlations on the network controllability is well studied for directed networks,it is not yet very clear for the case of undirected networks.To explore the impact of degree correlations on the controllability of undirected networks and their corresponding generalized (bidirectional and directed) networks,in this paper,we use the simulated annealing algorithm to change the network degree correlation coefficients by link rewiring.First,the undirected Erdős-Rényi random network and the modified scale-free network are taken as example models to be investigated.Numerical simulations show that the controllability measure (density of driver nodes) of undirected networks decreases monotonically with the increase of the degree correlation coefficient under a constant degree distribution.Specifically,when the degree correlation coefficient changes from -1 to 0,the controllability measure decreases rapidly;while the decrease in the controllability measure is not obvious when the degree correlation coefficient changes from 0 to 1.Next,the bidirectional networks and some directed networks are considered;in these networks,the in-degree of each node is equal to its out-degree,thus link rewiring results in the simultaneous changes of various degree correlations (i.e.,in-in,in-out,out-in,and out-out degree correlations).Further investigations show that these bidirectional and directed networks also follow the above rule,which is verified by the two real networks.The increase of the degree correlation coefficient in undirected networks also implies the increases of various degree correlation coefficients in the corresponding directed networks.Although the effect of a single degree correlation on the controllability of directed networks is clear,the comprehensive effect of the simultaneous changes in various degree correlations on the network controllability cannot be additively and therefore directly estimated by the relevant results in the corresponding directed networks;namely,the effect of the degree correlation on the controllability in an undirected network has its special rule.Some explanations are given for this phenomenon.Moreover,for a large sparse network without self-loops,no matter how assortative or disassortative it is,its structural controllability and exact controllability are verified to be almost the same.These studies will deepen the understanding of the relationship between the network controllability and the network structure.

Reference (30)

Catalog

    /

    返回文章
    返回