Abstract：The alternation of different types of edges (direction changed) and the addition of edges between different nodes in complex networks will have different effect on the controllability of the network. In order to better understand the influence of altering different edges and adding different edges on network controllability in directed networks, this paper proposes a classification method of edges. According to the node category and matching relationship, the directed edges are divided into twelve types, and the algorithm of identification is given. Based on the classification, the change law of network controllability (the number of driving nodes) is given when the edges of networks are altered and added. Through the simulation experiment of the model networks and the actual networks, the proportion of different types of edges is analyzed. When edges are altered and added, the changes in the number of driven nodes are analyzed in the model networks and the actual networks. The correctness of the theorems of this article are verified.
张虎林, 李成铁, 王立夫. 边转换与增加对有向网络能控性的影响[J]. 复杂系统与复杂性科学, 2023, 20(3): 11-19.
ZHANG Hulin, LI Chengtie, WANG Lifu. Influence of Alteration and Addition of Edges on Directed Network Controllability[J]. Complex Systems and Complexity Science, 2023, 20(3): 11-19.
[1] ZHANG Z K, LIU C, ZHAN X X, et al. Dynamics of information diffusion and its applications on complex networks[J]. Physics Reports, 2016, 651(1): 134. [2] ARIONAS S, BOMPARD E, CARBONE A, et al. Power grid vulnerability: a complex network approach[J]. Chaos, 2009, 19(1): 013119. [3] BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464 (7291): 10251028. [4] XU Z, HARRISS R. Exploring the structure of the US intercity passenger air transportation network: a weighted complex network approach[J]. Geojournal, 2008, 73(2): 87102. [5] PRILL R J, IGLESIAS P A, LEVCHENKO A. Dynamic properties of network motifs contribute to biological network organization[J]. Plos Biology, 2005, 3(11): 18811892. [6] WATTS, DUNCAN J. The “new” science of networks[J]. Annual Review of Sociology, 2004, 30(1): 243270. [7] ALBERT R, BARABASI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 4797. [8] NACHER J C, AKUTSU T. Structural controllability of unidirectional bipartite networks[J]. Scientific Reports, 2013, 3(1): 1647. [9] KEMPE D, KLEINBERG J, TARDOS E. Maximizing the spread of influence through a social network[J]. Theory of Computing, 2003, 11(4): 137146. [10] LIU Y Y, SLOTINE J J, BARABASI A L. Controllability of complex networks[J]. Nature, 2011, 473(7346): 167173. [11] TANG M, JIANG G, DENG G Q, et al. A new algorithm and application of solving maximum matching problem of bipartite graph[J]. Computer Systems & Applications, 2012, 21(3): 7275. [12] LI J, WANG S Y. An algorithm for constructing the maximum matching graphs on bigraphs[J]. Acta Electronica Sinica, 2010, 38(1): 161166. [13] YUAN Z, ZHAO C, DI Z, et al. Exact controlability of complex networks[J]. Nature Communications, 2013, 4(2447): 2447. [14] PóSFAI M, HÖVEL P. Structural controllability of temporal networks[J]. New Journal of Physics, 2014, 16(12): 123055. [15] PóSFAI M, GAO J, CORNELIUS S P, et al. Controllability of multiplex, multi-time-scale networks[J]. Physical Review E, 2016, 94(3): 032316. [16] MENARA T, BASSETT D, PASQUALETTI F. Structural controllability of symmetric networks[J]. IEEE Transactions on Automatic Control, 2019, 64 (9): 37403747. [17] YANG Y. Research progress in enhancing the controllability of complex networks[J]. Discrete Dynamics in Nature and Society, 2020(3): 18. [18] CHEN X, PEQUITO S, PAPPAS G J, et al. Minimal edge addition for network controllability[J]. IEEE Transactions on Control of Network Systems, 2018, 6(1): 312323. [19] MENICHETTI G, GIULIA, DALL′ASTA, et al. The controllability of networks is determined by the density of low in-degree and low out- degree nodes[DB/OL].[20210624].http://arxiv.org/abs/1405.4365v2. [20] ZHANG Y, ZHOU T. Minimal structural perturbations for controllability of a networked system: complexities and approximations [J]. International Journal of Robust and Nonlinear Control, 2019,29(7291): 41914208. [21] 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. [22] WANG X, XIANG L. Optimizing network controllability with minimum cost[J]. Complexity, 2021(3): 113. [23] RONG L, LIU J. A heuristic algorithm for enhancing the robustness of scale-free networks based on edge classification[J]. Physica A, 2018, 503: 503515. [24] HOU L, LAO S, SMALL M, Xiao Y. Enhancing complex network controllability by minimum link direction reversal[J]. Physics Letters A, 2015, 379(20/21): 13211325. [25] XIAO Y D, LAO S Y, HOU L L, et al. Edge orientation for optimizing controllability of complex networks[J]. Physical Review E, 2014, 90(4): 042804. [26] XIAO Y, LAO S Y, HOU L, et al. Effects of edge directions on the structural controllability of complex networks[J]. Plos One, 2015, 10(8): 0135282. [27] SON S W, KIM B J, HONG H, et al. Dynamics and directionality in complex networks[J]. Physical Review Letters, 2009, 103(22): 228702. [28] HAO Y, JIA L, WANG Y. Edge attack strategies in interdependent scale-free networks[J]. Physica A, 2019, 540(1): 122759. [29] LOU Y, WANG L, CHEN G. A framework of hierarchical attacks to network controllability[J]. Communications in Nonlinear Science and Numerical Simulation, 2021, 98(7346): 105780. [30] HOPCROFT J E, KARP R M. An n5/2 algorithm for maximum matching in bipartite graphs[C] // Meyer A R, Fischer M J. 12th Annual Symposium on Switching and Automata Theory. East Lansing: IEEE, 1971: 122125. [31] JIA T, LIU Y Y, CSóKA E, et al. Emergence of bimodality in controlling complex networks[J]. Nature Communications, 2013, 4(1): 2002. [32] ERDOS P, RENYI A. On random graphs[J]. Publicationes Mathematicae, 1959, 6(1): 290297. [33] BARABÁSI A-L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286 (5439): 509512. [34] KUNEGIS J. KONECT [EB/OL]. (2013530)[20211130]. http://konect.cc/networks/. [35] WASSERMAN, FAUST. Social network [EB/OL]. (20031011)[20211130]. http://vlado.fmf.uni-lj.si/pub/networks/data/.
