Effect of degree correlation on edge controllability of real networks

doi:10.1088/1674-1056/ab99ab

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_{D}^{r e a l}$ obtained directly and $n_{D}^{r a n d}$ of real networks with no degree correlation. (b) The fraction of driven edges $m_{D}^{r e a l}$ obtained directly and $m_{D}^{r a n d}$ of real networks with no degree correlation. (c) and (d) The differences $Δ_{n} = n_{D}^{r a n d} - n_{D}^{r e a l}$ and $Δ_{m} = m_{D}^{r a n d} - m_{D}^{r e a l}$ 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 K_in = {0,1,2,3} and out-degree sequence K_out = {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}^{-} < k_{j}^{+}$ . Its generated network in (e) has $N_{D}^{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}^{-} \geq k_{j}^{+}$ . Its generated network in (f) has $N_{D}^{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_{D}^{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}^{-} < k_{j}^{+}$ , and 0 for other edges. Its generated network in (h) has $M_{D}^{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_{D}^{r e a l}$ obtained directly and the controllability limit ( $n_{D}^{U}$ and $n_{D}^{L}$ ) of real networks. (b) The fraction of driven edges $m_{D}^{r e a l}$ obtained directly and the controllability limit ( $m_{D}^{U}$ and $m_{D}^{L}$ ) of real networks. (c) and (d) The differences $n_{D}^{U} - n_{D}^{L}$ and $m_{D}^{U} - m_{D}^{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_{D}^{r e a l}$	$m_{D}^{r e a l}$	$n_{D}^{r a n d}$	$m_{D}^{r a n d}$	$n_{D}^{U}$	$n_{D}^{L}$	$m_{D}^{U}$	$m_{D}^{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_{D}^{r e a l}$ and $m_{D}^{r e a l}$ ), after randomization ( $n_{D}^{r a n d}$ and $m_{D}^{r a n d}$ ), and the controllability limits ( $n_{D}^{U}$ , $n_{D}^{L}$ , $m_{D}^{U}$ and $m_{D}^{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_{N D}^{U}$ (red) and $P_{N D}^{L}$ (blue) in [(a), (c)] model networks and (e) real networks. The Pearson correlation coefficient $P_{M D}^{U}$ (green) and $P_{M D}^{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]	http://vlado.fmf.uni-lj.si/pub/networks/data/cite/default.htm
[40]	http://www.cise.ufl.edu/research/sparse/matrices/Pajek/Kohonen.html
[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]	http://vlado.fmf.uni-lj.si/pub/networks/data/mix/USAir97.net

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

Viewed

Full text

Abstract

Cited

Metrics
Related Articles

Effect of degree correlation on edge controllability of real networks

Cite this article:

Online attention