边转换与增加对有向网络能控性的影响

张虎林; 李成铁; 王立夫; 张虎林; 李成铁; 王立夫

doi:10.13306/j.1672-3813.2023.03.002

复杂系统与复杂性科学 >

2023 , Vol. 20 >Issue 3: 11 - 19

DOI: https://doi.org/10.13306/j.1672-3813.2023.03.002

边转换与增加对有向网络能控性的影响

张虎林 ,
李成铁 ,
王立夫 ,
张虎林 ,
李成铁 ,
王立夫

展开

东北大学秦皇岛分校控制工程学院,河北秦皇岛 066004

张虎林(1999),男,河北廊坊人,硕士研究生,主要研究方向为复杂网络能控性。

收稿日期: 2021-12-29

修回日期: 2022-03-24

网络出版日期: 2023-10-08

基金资助

中央高校基本科研业务费专项资金(N2023022)

收起

Influence of Alteration and Addition of Edges on Directed Network Controllability

ZHANG Hulin ,
LI Chengtie ,
WANG Lifu ,
ZHANG Hulin ,
LI Chengtie ,
WANG Lifu

Expand

School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China

Received date: 2021-12-29

Revised date: 2022-03-24

Online published: 2023-10-08

Fold

摘要

复杂网络的不同类型边转换(方向改变)和在不同节点间增加边对网络能控性有不同影响,为了更好地了解有向网络边转换和增加对网络能控性影响,提出一种边分类方法,把边根据节点类别和匹配关系分成12种类型,并给出辨识算法。基于此分类给出网络边转换和增加时网络能控性(驱动节点数目)的变化规律。通过模型网络和实际网络分析了每种边在网络中的比例,并分析了边转换和增加时驱动节点数目变化。结果验证了定理的正确性。

关键词： 网络能控性; 驱动节点; 最大匹配; 转换边; 增加边

本文引用格式

张虎林 , 李成铁 , 王立夫 , 张虎林 , 李成铁 , 王立夫 . 边转换与增加对有向网络能控性的影响[J]. 复杂系统与复杂性科学, 2023 , 20(3) : 11 -19 . DOI: 10.13306/j.1672-3813.2023.03.002

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.

Key words： network controllability; driver node; maximum matching; alteration of edges; addition of edges

参考文献

[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 n^5/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/.

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract

参考文献