On the Structural Controllability of Temporal Complex Networks
PAN Yujian, LI Xiang
Lab of Adaptive Networks and Control, Department of Electronic Engineering, School of Information Science and Engineering, Fudan University, Shanghai 200433, China
Abstract：With reviewing the existing studies on the structural controllability of static networks, we explore the approach to understand and analyze the structural controllability of temporal networks. We firstly reveal the characteristics of the structural controllability of temporal networks by the improved maximum matching method; then, by mapping a temporal into a LTV system, we give a framework to study the structural controllability of temporal networks; finally, on the basis of this framework, we further analyze the upper and lower bounds of network nodes′ controlling centrality in the case of single controller.
潘玉剑, 李翔. 时效复杂网络结构可控性研究[J]. 复杂系统与复杂性科学, 2015, 12(2): 23-31.
PAN Yujian, LI Xiang. On the Structural Controllability of Temporal Complex Networks[J]. Complex Systems and Complexity Science, 2015, 12(2): 23-31.
[1] Kalman R E. Mathematical description of linear dynamical systems[J]. Journal of the Society for Industrial & Applied Mathematics, Series A: Control, 1963, 1(2): 152-192. [2] Siljak D. Decentralized Control of Complex Systems[M]. New York: Academic Press, 1991. [3] 陈关荣. 漫谈系统与网络[J]. 复杂系统与复杂性科学, 2010, 7(2): 1-4. Chen Guanrong. A talk about systems and networks[J]. Complex systems and complexity science, 2010, 7(2): 1-4. [4] Erdös P, Rényi A. On random graphs I[J]. Publ Math Debrecen, 1959, 6: 290-297. [5] Erdös P, Rényi A. On the evolution of random graphs[J]. Selected Papers of Alfréd Rényi, 1976, 2: 482-525. [6] Lin C T. Structural controllability[J]. Automatic Control, IEEE Transactions on, 1974, 19(3): 201-208. [7] Shields R W, Pearson J B. Structural controllability of multiinput linear systems[J]. IEEE Trans on AC,1976,21(2):203-212. [8] Mayeda H. On structural controllability theorem[J]. Automatic Control, IEEE Transactions on, 1981, 26(3): 795-798. [9] Watts D J, Strogatz S H. Collective dynamics of ‘small-world′networks[J]. Nature, 1998, 393(6684): 440-442. [10] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512. [11] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167-173. [12] 陈关荣. 复杂动态网络环境下控制理论遇到的问题与挑战[J]. 自动化学报, 2013, 39(4): 312-321. Chen Guanrong. Problems and challenges in control theory under complex network environments[J]. Acta Automatica Sinica, 2013, 39(4): 312-321. [13] 席裕庚. 大系统控制理论与复杂网络——探索与思考[J]. 自动化学报, 2013, 39(11): 1758-1768. Xi Yugeng. Large-scale systems control and complex networks-exploration and thinking[J]. Acta Automatica Sinica, 2013, 39(11): 1758-1768. [14] Wang W X, Ni X, Lai Y C, et al. Optimizing controllability of complex networks by minimum structural perturbations[J]. Physical Review E, 2012, 85(2): 026115. [15] Liu Y Y, Slotine J J, Barabási A L. Control centrality and hierarchical structure in complex networks[J]. Plos one, 2012, 7(9): e44459. [16] Nepusz T, Vicsek T. Controlling edge dynamics in complex networks[J]. Nature Physics, 2012, 8(7): 568-573. [17] Yan G, Ren J, Lai Y C, et al. Controlling complex networks: How much energy is needed?[J]. Physical Review Letters, 2012, 108(21): 218703. [18] Sun J, Motter A E. Controllability transition and nonlocality in network control[J]. Physical Review Letters, 2013, 110(20): 208701. [19] Yuan Z, Zhao C, Di Z, et al. Exact controllability of complex networks[J]. Nature Communications, 2013, 4:2447. [20] Ruths J, Ruths D. Control profiles of complex networks[J]. Science, 2014, 343(6177): 1373-1376. [21] Lombardi A, Hörnquist M. Controllability analysis of networks[J]. Physical Review E, 2007, 75(5): 056110. [22] Hopcroft J E, Karp R M. An n^5/2 algorithm for maximum matchings in bipartite graphs[J]. SIAM Journal on Computing, 1973, 2(4): 225-231. [23] Mayeda H, Yamada T. Strong structural controllability[J]. SIAM Journal on Control and Optimization, 1979, 17(1): 123-138. [24] Reinschke K J, Svaricek F, Wend H D. On strong structural controllability of linear systems[C]//Proceedings of the 31st IEEE Conference on Decision and Control. IEEE, 1992: 203-208. [25] Jarczyk J C, Svaricek F, Alt B. Strong structural controllability of linear systems revisited[C]//CDC-ECE, 2011: 1213-1218. [26] Chapman A, Mesbahi M. On strong structural controllability of networked systems: a constrained matching approach[C]//American Control Conference (ACC), IEEE, 2013: 6126-6131. [27] Pan Y, Li X, Zhan J. On the priority maximum matching of structural controllability of temporal networks[C]//Control Conference (CCC), 2013 32nd Chinese, IEEE, 2013: 1164-1169. [28] Pan Y, Li X. Towards a graphic tool of the structural controllability of temporal networks[C]//International Symposium on Circuits and Systems (ISCAS), Australia IEEE, 2014. [29] Pan Y, Li X. Structural controllability and controlling centrality of temporal networks[J]. PloS one, 2014, 9(4): e94998. [30] Holme P, Saramäki J. Temporal networks[J]. Physics Reports, 2012, 519(3): 97-125. [31] Kim H, Anderson R. Temporal node centrality in complex networks[J]. Physical Review E, 2012, 85(2): 026107. [32] Isella L, Stehlé J, Barrat A, et al. What′s in a crowd? Analysis of face-to-face behavioral networks[J]. Journal of Theoretical Biology, 2011, 271(1): 166-180. [33] Zhang Y, Wang L, Zhang Y Q, et al. Towards a temporal network analysis of interactive WiFi users[J]. EPL (Europhysics Letters), 2012, 98(6): 68002. [34] Zhang Y Q, Li X. Temporal dynamics and impact of event interactions in cyber-social populations[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2013, 23(1): 013131. [35] Shah D, Zaman T. Rumors in a network: who′s the culprit?[J]. IEEE Transactions on Information Theory, 2011, 57(8): 5163-5181. [36] Pinto P C, Thiran P, Vetterli M. Locating the source of diffusion in large-scale networks[J]. Physical Review Letters, 2012, 109(6): 068702. [37] Li X, Zhang Y Q, Vasilakos A V. Discovering and Predicting Temporal Patterns of WiFi-Interactive Social Populations[M]//Wu J, Wang Y S. Opportunistic Social Mobile Networks, CRC Press, 2014.
