Please wait a minute...
Chin. Phys. B, 2020, Vol. 29(10): 100202    DOI: 10.1088/1674-1056/ab99ab
General Prev   Next  

Effect of degree correlation on edge controllability of real networks

Shu-Lin Liu(刘树林) and Shao-Peng Pang(庞少鹏)†
1 School of Electrical Engineering and Automation, Qilu University of Technology (Shandong Academy of Science), Jinan 250353, China
Abstract  

We use the controllability limit theory to study impact of correlation between in- and out-degrees (degree correlation) on edge controllability of real networks. Simulation results and analytic calculations show that the degree correlation plays an important role in the edge controllability of real networks, especially dense real networks. The upper and lower controllability limits hold for all kinds of real networks. Any edge controllability in between the limits is achievable by properly adjusting the degree correlation. In addition, we find that the edge dynamics in some real networks with positive degree correlation may be difficult to control, and explain the rationality of this anomaly based on the controllability limit theory.

Keywords:  complex network      edge controllability      degree correlation      controllability limit  
Received:  05 April 2020      Revised:  24 May 2020      Accepted manuscript online:  05 June 2020
PACS:  02.30.Yy (Control theory)  
  89.75.Fb (Structures and organization in complex systems)  
Corresponding Authors:  Corresponding author. E-mail: shaopengpang@qlu.edu.cn   
About author: 
†Corresponding author. E-mail: shaopengpang@qlu.edu.cn
* Project supported by the National Natural Science Foundation of China (Grant No. 61903208).

Cite this article: 

Shu-Lin Liu(刘树林) and Shao-Peng Pang(庞少鹏)† Effect of degree correlation on edge controllability of real networks 2020 Chin. Phys. B 29 100202

Fig. 1.  

Effect of degree correlation on the edge controllability of real networks. (a) The fraction of driver nodes $ {n}_{{\rm{D}}}^{{\rm{real}}} $ obtained directly and $ {n}_{{\rm{D}}}^{{\rm{rand}}} $ of real networks with no degree correlation. (b) The fraction of driven edges $ {m}_{{\rm{D}}}^{{\rm{real}}} $ obtained directly and $ {m}_{{\rm{D}}}^{{\rm{rand}}} $ of real networks with no degree correlation. (c) and (d) The differences $ {\varDelta }_{n}={n}_{{\rm{D}}}^{{\rm{rand}}}-{n}_{{\rm{D}}}^{{\rm{real}}} $ and $ {\varDelta }_{m}={m}_{{\rm{D}}}^{{\rm{rand}}}-{m}_{{\rm{D}}}^{{\rm{real}}} $ as the function of the Pearson correlation coefficient P of real networks. All the numerical results are obtained by averaging over 50 independent networks realizations. See Table 1 for details.

Fig. 2.  

Controllability limit theory. The method of calculating the controllability limits of a network with in-degree sequence Kin = {0,1,2,3} and out-degree sequence Kout = {1,1,2,2}. (a) In the bipartite graph H, the node i from in-degree sequence and the node j from out-degree sequence are connected if $ {k}_{i}^{-}\lt {k}_{j}^{+} $ . Its generated network in (e) has $ {N}_{{\rm{D}}}^{{\rm{U}}}=2 $ . (b) In the bipartite graph $ \bar{H} $ , the node i from in-degree sequence and the node j from out-degree sequence will be connected if $ {k}_{i}^{-}\ge {k}_{j}^{+} $ . Its generated network in (f) has $ {N}_{{\rm{D}}}^{{\rm{L}}}=1 $ . (c) The weighted bipartite graph H* has the same topological structure as H, and the weight of each edge is $ {k}_{j}^{+}-{k}_{i}^{-} $ . Its generated network in (g) has $ {M}_{{\rm{D}}}^{{\rm{U}}}=3 $ . (d) The weighted bipartite graph $ \bar{{H}^{* }} $ is generated by connecting arbitrary two nodes, and assigning the weight $ {k}_{i}^{-}-{k}_{j}^{+} $ to the edges satisfying $ {k}_{i}^{-}\lt {k}_{j}^{+} $ , and 0 for other edges. Its generated network in (h) has $ {M}_{{\rm{D}}}^{{\rm{L}}}=1 $ . Note that the matching nodes of the generated networks are from the matched edges in the maximum matching, and other nodes of the generated networks are combined randomly.

Fig. 3.  

Controllability limit of real networks. (a) The fraction of driver nodes $ {n}_{{\rm{D}}}^{{\rm{real}}} $ obtained directly and the controllability limit ($ {n}_{{\rm{D}}}^{{\rm{U}}} $ and $ {n}_{{\rm{D}}}^{{\rm{L}}} $ ) of real networks. (b) The fraction of driven edges $ {m}_{{\rm{D}}}^{{\rm{real}}} $ obtained directly and the controllability limit ($ {m}_{{\rm{D}}}^{{\rm{U}}} $ and $ {m}_{{\rm{D}}}^{{\rm{L}}} $ ) of real networks. (c) and (d) The differences $ {n}_{{\rm{D}}}^{{\rm{U}}}-{n}_{{\rm{D}}}^{{\rm{L}}} $ and $ {m}_{{\rm{D}}}^{{\rm{U}}}-{m}_{{\rm{D}}}^{{\rm{L}}} $ versus the average degree 〈k〉 of real networks. The numbers in (a) and (b) refer to the network indices in Table 1.

Fig. 4.  

Anomaly in edge controllability of real networks. (a) The Pearson correlation coefficient P and the differences Δn of real networks. (b) The Pearson correlation coefficient P and the differences Δm of real networks. All the numerical results are obtained by averaging over 50 independent networks in realizations. The numbers refer to the network indices in Table 1.

Type No. Name N M P $ {n}_{{\rm{D}}}^{{\rm{real}}} $ $ {m}_{{\rm{D}}}^{{\rm{real}}} $ $ {n}_{{\rm{D}}}^{{\rm{rand}}} $ $ {m}_{{\rm{D}}}^{{\rm{rand}}} $ $ {n}_{{\rm{D}}}^{{\rm{U}}} $ $ {n}_{{\rm{D}}}^{{\rm{L}}} $ $ {m}_{{\rm{D}}}^{{\rm{U}}} $ $ {m}_{{\rm{D}}}^{{\rm{L}}} $
Regulatory 1 Ownership-USCorp[28] 8497 6726 −0.031 0.136 0.924 0.086 0.848 0.159 0.028 1.000 0.738
2 TRN-EC-2[29] 423 578 −0.082 0.220 0.829 0.166 0.762 0.274 0.071 0.879 0.545
3 TRN-Yeast-1[30] 4684 15451 0.044 0.052 0.947 0.049 0.947 0.064 0.025 0.984 0.803
4 TRN-Yeast-2[29] 688 1079 –0.236 0.177 0.952 0.138 0.841 0.190 0.063 0.968 0.610
Trust 5 Prison inmate[31] 67 182 0.201 0.403 0.319 0.450 0.359 0.761 0.179 0.511 0.110
6 Wiki Vote[32] 7115 103689 0.318 0.281 0.653 0.279 0.834 0.335 0.066 0.987 0.192
Food web 7 St.Marks[33] 45 224 −0.292 0.533 0.563 0.479 0.483 0.711 0.156 0.701 0.143
8 Seagrass[34] 49 226 −0.192 0.449 0.518 0.441 0.46 0.714 0.102 0.655 0.097
9 Grassland[35] 88 137 −0.179 0.318 0.606 0.302 0.559 0.341 0.148 0.620 0.314
10 Ythan[35] 135 601 0.168 0.304 0.597 0.333 0.637 0.474 0.052 0.844 0.195
11 Silwood[36] 154 370 0.014 0.188 0.797 0.174 0.806 0.214 0.084 0.897 0.508
12 Little Rock[37] 183 2494 −0.138 0.639 0.603 0.654 0.601 0.831 0.497 0.818 0.299
Electronic 13 S208a[29] 122 189 −0.177 0.451 0.344 0.430 0.326 0.549 0.311 0.413 0.201
circuits 14 s420a[29] 252 399 −0.154 0.456 0.348 0.439 0.327 0.560 0.325 0.416 0.206
15 s838a[29] 512 819 −0.146 0.459 0.350 0.441 0.327 0.564 0.332 0.418 0.208
Neuronal 16 C. elegans[38] 297 2359 0.291 0.549 0.374 0.494 0.477 0.923 0.081 0.639 0.069
Citation 17 Small World[39] 233 1988 −0.094 0.210 0.729 0.206 0.735 0.309 0.047 0.869 0.469
18 SciMet[39] 2729 10416 0.068 0.360 0.623 0.352 0.638 0.613 0.037 0.830 0.153
19 Kohonen[40] 3772 12731 0.044 0.230 0.715 0.215 0.724 0.381 0.029 0.876 0.436
Internet 20 Political blogs[41] 1224 19090 0.379 0.619 0.525 0.553 0.710 0.870 0.165 0.908 0.162
21 p2p-1[42] 10876 39994 0.145 0.334 0.591 0.344 0.647 0.381 0.255 0.870 0.325
22 p2p-2[42] 8846 31839 0.101 0.344 0.628 0.344 0.659 0.387 0.265 0.878 0.352
23 p2p-3[42] 8717 31525 0.107 0.343 0.625 0.344 0.658 0.383 0.264 0.878 0.347
Organizational 24 Freeman-1[43] 34 695 0.642 0.353 0.111 0.454 0.199 0.735 0.118 0.285 0.047
25 Consulting[44] 46 879 0.482 0.522 0.150 0.497 0.266 0.848 0.109 0.369 0.078
Language 26 English words[31] 7381 46281 0.857 0.158 0.210 0.326 0.755 0.479 0.003 0.862 0.087
27 French words[31] 8325 24295 0.905 0.157 0.216 0.254 0.676 0.333 0.009 0.736 0.092
Transportation 28 USair97[45] 332 2126 0.608 0.437 0.400 0.440 0.689 0.762 0.030 0.861 0.045
Table 1.  

Simulation results of real networks. For each real network, we show its type, name, nodes’ number N, edges’ number M, the Pearson correlation coefficient P, the fraction of driver nodes and driven edges calculated in the real network ($ {n}_{{\rm{D}}}^{{\rm{real}}} $ and $ {m}_{{\rm{D}}}^{{\rm{real}}} $ ), after randomization ($ {n}_{{\rm{D}}}^{{\rm{rand}}} $ and $ {m}_{{\rm{D}}}^{{\rm{rand}}} $ ), and the controllability limits ($ {n}_{{\rm{D}}}^{{\rm{U}}} $ , $ {n}_{{\rm{D}}}^{{\rm{L}}} $ , $ {m}_{{\rm{D}}}^{{\rm{U}}} $ and $ {m}_{{\rm{D}}}^{{\rm{L}}} $ ).

Fig. 5.  

Anomaly in edge controllability. The range of Pearson correlation coefficient P in (a)–(d) model networks and (e)–(f) real networks. The Pearson correlation coefficient $ {P}_{{\rm{ND}}}^{{\rm{U}}} $ (red) and $ {P}_{{\rm{ND}}}^{{\rm{L}}} $ (blue) in [(a), (c)] model networks and (e) real networks. The Pearson correlation coefficient $ {P}_{{\rm{MD}}}^{{\rm{U}}} $ (green) and $ {P}_{{\rm{MD}}}^{{\rm{L}}} $ (orange) in [(b), (d)] model networks and (f) real networks. The model network is generated by given degree distribution, where in-degree follows exponent distribution and out-degree follows Poisson distribution in (a) and (b), and in-degree follows Poisson distribution and out-degree follows exponent distribution in (c) and (d). See Appendix for how to construct a model network. All the numerical results are obtained by averaging over 50 independent networks in realizations. The numbers in (e)–(f) refer to the network indices in Table 1.

[1]
Sorrentino F, Di Bernardo M, Garofalo F, Chen G 2007 Phys. Rev. E 75 046103 DOI: 10.1103/PhysRevE.75.046103
[2]
Lombardi A, Hörnquist M 2007 Phys. Rev. E 75 056110 DOI: 10.1103/PhysRevE.75.056110
[3]
Chui C K, Chen G 2012 Linear systems and optimal control Berlin Springer Science & Business Media
[4]
Lin C T 1974 IEEE Trans. Automat. Contr. 19 201 DOI: 10.1109/TAC.1974.1100557
[5]
Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167 DOI: 10.1038/nature10011
[6]
Yuan Z Z, Zhao C, Di Z R, Wang W X, Lai Y C 2013 Nat. Commun. 4 2447 DOI: 10.1038/ncomms3447
[7]
Cornelius S P, Kath W L, Motter A E 2013 Nat. Commun. 4 1942 DOI: 10.1038/ncomms2939
[8]
Olshevsky A 2014 IEEE Trans. Control Netw. Syst. 1 249 DOI: 10.1109/TCNS.2014.2337974
[9]
Yan G, Tsekenis G, Barzel B, Slotine J J, Liu Y Y, Barabási A L 2015 Nat. Phys. 11 779 DOI: 10.1038/nphys3422
[10]
Liu Y Y, Barabási A L 2016 Rev. Mod. Phys. 88 035006 DOI: 10.1103/RevModPhys.88.035006
[11]
Li A M, Cornelius S P, Liu Y Y, Wang L, Barabási A L 2017 Science 358 1042 DOI: 10.1126/science.aai7488
[12]
Nepusz T, Vicsek T 2012 Nat. Phys. 8 568 DOI: 10.1038/nphys2327
[13]
Slotine J J, Liu Y Y 2012 Nat. Phys. 8 512 DOI: 10.1038/nphys2342
[14]
Pang S P, Hao F, Wang W X 2012 Phys. Rev. E 94 052310 DOI: 10.1103/PhysRevE.94.052310
[15]
Pang S P, Wang W X, Hao F, Lai Y C 2017 Sci. Rep. 7 4224 DOI: 10.1038/s41598-017-04463-5
[16]
Su H, Wu H, Chen X, Chen M Z 2017 IEEE Transactions on Systems, Man, and Cybernetics: Systems 48 2242 DOI: 10.1109/TSMC.2017.2765678
[17]
Pang S P, Hao F 2017 Physica A 481 209 DOI: 10.1016/j.physa.2017.04.034
[18]
Pang S P, Hao F 2018 Physica A 512 14 DOI: 10.1016/j.physa.2018.08.011
[19]
Wu H, Lam J, Su H 2019 IEEE Transactions on Systems, Man, and Cybernetics: Systems August 14, 2019 1 10 DOI: 10.1109/TSMC.2019.2931411
[20]
Pang S P, Li C, Fang C, Han G Z 2019 Physica A 528 121273 DOI: 10.1016/j.physa.2019.121273
[21]
Xiang L, Chen G R 2019 Adv. Complex Sys. 22 1950017 DOI: 10.1142/S0219525919500176
[22]
Pang S P, Wang W X, Hao F 2019 Phys. Rev. E 100 022318 DOI: 10.1103/PhysRevE.100.022318
[23]
Li C, Pang S P 2020 IEEE Access 8 63559 DOI: 10.1109/Access.6287639
[24]
Schwartz N, Cohen R, Ben-Avraham D, Barabási A L, Havlin S 2020 Phys. Rev. E 66 015104 DOI: 10.1103/PhysRevE.66.015104
[25]
Bianconi G, Gulbahce N, Motter A E 2008 Phys. Rev. Lett. 100 118701 DOI: 10.1103/PhysRevLett.100.118701
[26]
Pósfai M, Liu Y Y, Slotine J J, Barabási A L 2013 Sci. Rep. 3 1067 DOI: 10.1038/srep01067
[27]
Benesty J, Chen J, Huang Y, Cohen I 2009 Noise reduction in speech processing Berlin Springer Science & Business Media
[28]
Kim Norlen G L, Gebbie M, Chuang J 2002 Proceedings of International Telecommunications Society 14th Biennial Conference August 2002 South Korea
[29]
Milo R, Shenorr S S, Itzkovitz S, Kashtan N, Chklovskii D B, Alon U 2002 Science 298 824 DOI: 10.1126/science.298.5594.824
[30]
Balaji S, Babu M M, Iyer L M, Luscombe N M, Aravind L 2006 J. Mol. Biol. 360 213 DOI: 10.1016/j.jmb.2006.04.029
[31]
Milo R, Itzkovitz S, Kashtan N, Levitt R, Shen-Orr S, Ayzenshtat I, Sheffer M, Alon U 2004 Science 303 1538 DOI: 10.1126/science.1089167
[32]
Leskovec J, Lang K J, Dasgupta A, Mahoney M 2009 Internet Mathematics 6 29 DOI: 10.1080/15427951.2009.10129177
[33]
Baird D, Luczkovich J, Christian R R 1998 Coastal and Shelf Science 47 329 DOI: 10.1006/ecss.1998.0360
[34]
Christian R R, Luczkovich J J 1998 Ecological Modelling 117 99 DOI: 10.1016/S0304-3800(99)00022-8
[35]
Dunne J A, Williams R J, Martinez N D 2002 Proc. Natl. Acad. Sci. USA 99 12917 DOI: 10.1073/pnas.192407699
[36]
Montoya J M, Sole R V 2002 J. Theor. Biol. 214 405 DOI: 10.1006/jtbi.2001.2460
[37]
Martinez N D 1991 Ecological Monographs 61 367 DOI: 10.2307/2937047
[38]
Watts D J, Strogatz S H 1998 Nature 393 440 DOI: 10.1038/30918
[39]
[40]
[41]
Adamic L A, Glance N 2005 Proceedings of the 3rd international workshop on link discovery August 2005 New York, USA 36 43
[42]
Leskovec J, Kleinberg J, Faloutsos C 2007 ACM Transactions on Knowledge Discovery from Data 1 2 DOI: 10.1145/1217299.1217301
[43]
Freeman S C, Freeman L C 1979 The networkers network: A study of the impact of a new communications medium on sociometric structure Social Science Research Reports No. 46 University of California Irvine, CA
[44]
Cross R L, Cross R L, Parker A 2004 The hidden power of social networks: Understanding how work really gets done in organizations Boston Harvard Business Press
[45]
[1] Analysis of cut vertex in the control of complex networks
Jie Zhou(周洁), Cheng Yuan(袁诚), Zu-Yu Qian(钱祖燏), Bing-Hong Wang(汪秉宏), and Sen Nie(聂森). Chin. Phys. B, 2023, 32(2): 028902.
[2] Vertex centrality of complex networks based on joint nonnegative matrix factorization and graph embedding
Pengli Lu(卢鹏丽) and Wei Chen(陈玮). Chin. Phys. B, 2023, 32(1): 018903.
[3] Effect of observation time on source identification of diffusion in complex networks
Chaoyi Shi(史朝义), Qi Zhang(张琦), and Tianguang Chu(楚天广). Chin. Phys. B, 2022, 31(7): 070203.
[4] An extended improved global structure model for influential node identification in complex networks
Jing-Cheng Zhu(朱敬成) and Lun-Wen Wang(王伦文). Chin. Phys. B, 2022, 31(6): 068904.
[5] Characteristics of vapor based on complex networks in China
Ai-Xia Feng(冯爱霞), Qi-Guang Wang(王启光), Shi-Xuan Zhang(张世轩), Takeshi Enomoto(榎本刚), Zhi-Qiang Gong(龚志强), Ying-Ying Hu(胡莹莹), and Guo-Lin Feng(封国林). Chin. Phys. B, 2022, 31(4): 049201.
[6] Explosive synchronization: From synthetic to real-world networks
Atiyeh Bayani, Sajad Jafari, and Hamed Azarnoush. Chin. Phys. B, 2022, 31(2): 020504.
[7] Robust H state estimation for a class of complex networks with dynamic event-triggered scheme against hybrid attacks
Yahan Deng(邓雅瀚), Zhongkai Mo(莫中凯), and Hongqian Lu(陆宏谦). Chin. Phys. B, 2022, 31(2): 020503.
[8] Finite-time synchronization of uncertain fractional-order multi-weighted complex networks with external disturbances via adaptive quantized control
Hongwei Zhang(张红伟), Ran Cheng(程然), and Dawei Ding(丁大为). Chin. Phys. B, 2022, 31(10): 100504.
[9] Explosive synchronization in a mobile network in the presence of a positive feedback mechanism
Dong-Jie Qian(钱冬杰). Chin. Phys. B, 2022, 31(1): 010503.
[10] LCH: A local clustering H-index centrality measure for identifying and ranking influential nodes in complex networks
Gui-Qiong Xu(徐桂琼), Lei Meng(孟蕾), Deng-Qin Tu(涂登琴), and Ping-Le Yang(杨平乐). Chin. Phys. B, 2021, 30(8): 088901.
[11] Complex network perspective on modelling chaotic systems via machine learning
Tong-Feng Weng(翁同峰), Xin-Xin Cao(曹欣欣), and Hui-Jie Yang(杨会杰). Chin. Phys. B, 2021, 30(6): 060506.
[12] Dynamical robustness of networks based on betweenness against multi-node attack
Zi-Wei Yuan(袁紫薇), Chang-Chun Lv(吕长春), Shu-Bin Si(司书宾), and Dong-Li Duan(段东立). Chin. Phys. B, 2021, 30(5): 050501.
[13] Exploring individuals' effective preventive measures against epidemics through reinforcement learning
Ya-Peng Cui(崔亚鹏), Shun-Jiang Ni (倪顺江), and Shi-Fei Shen(申世飞). Chin. Phys. B, 2021, 30(4): 048901.
[14] Improving robustness of complex networks by a new capacity allocation strategy
Jun Liu(刘军). Chin. Phys. B, 2021, 30(1): 016401.
[15] Manufacturing enterprise collaboration network: An empirical research and evolutionary model
Ji-Wei Hu(胡辑伟), Song Gao(高松), Jun-Wei Yan(严俊伟), Ping Lou(娄平), Yong Yin(尹勇). Chin. Phys. B, 2020, 29(8): 088901.
No Suggested Reading articles found!