Robustness of Controlling and Observing Edge Dynamics in Complex Networks 1 Zhi Tian1, Shaopeng Pang1*, Peng Ji1*, Weigang Ma2 1 School of Information and Automation Engineering Qilu University of Technology (Shandong Academy of Sciences) Ji Nan, China 2 Jinan Rail Transit Group 1ST Operation Co.,Ltd. Ji Nan, China Abstract The dynamic processes on the edges of complex networks are closely related to various real- world situations. In recent years, more and more scholars have devoted themselves to the study of the edge dynamics in complex networks and achieved fruitful results. The robustness of controlling the edge dynamics in complex networks has been extensively studied. However, there is no relevant work to study the robustness of observability. In this paper, we develop a framework based on the edge classification to study the robustness of controlling and observing the edge dynamics in complex networks. We apply the framework to model networks and give a theoretical formulation of the edge classification. By comparing with the robustness that only considers the structural controllability, we find that this framework enables us to have a more comprehensive analysis method for the edge failure problem in the edge dynamics of complex networks. Keywords complex network, edge dynamic, robustness, controllability, observability 1. INTRODUCTION In recent years, the node dynamics of complex networks [1-10] has attracted the attention of many scholars and made a lot of significant progress. Lin [11] proposed the structural controllability, which bypasses the need to measure system parameters, and studied network controllability based on the graph topology. Liu et al. [12] developed the structural controllability theory and proposed the minimum input theory based on the maximum matching to characterize the structural controllability. Due to the duality principle [13-14], many attributes of observability can be borrowed from controllability. The theoretical framework in [15] provides a new perspective for us to study the observability of complex networks. Nepusz et al. [16] extended the applicability of structural controllability to the edge dynamics of directed networks. Then Pang et al. [17] gave a general framework for the controllability of edge dynamics for arbitrary complex networks. In this paper, we develop a framework based on the edge classification to study the robustness of controlling and observing the edge dynamics in complex networks. This framework enables us to quantify the robustness by the edge classification. We study the effect of network topology on the robustness based on the simulation of model networks. In addition, we give the theoretical formulation of edge classification of model network. 2. EDGE DYNAMICS The directed graph containing 𝑁 nodes and 𝑀 edges is denoted as 𝐺(𝑉, 𝐸). The edge dynamics of complex network is described by the switch dynamics, where the state vector corresponds to the edge ICCEIC2022@3rd International Conference on Computer Engineering and Intelligent Control EMAIL: zhit518@163.com (Zhi Tian), pang_shao_peng@163.com (Shaopeng Pang), jipeng@qlu.edu.cn (Peng Ji), yhfx_mwg@163.com (Weigang Ma) Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 66 set, and each state corresponds to an edge. For any node in the network, its outgoing edge state is influenced by the incoming edge state, its own damping and external inputs, so we have: 𝑦 = 𝑆 𝑦 βˆ’ 𝜏 ⨂𝑦 + 𝜎 𝑒 , (1) where 𝑦 and 𝑦 are the outgoing and incoming edge state vectors of node 𝑣, respectively. 𝑆 is the switching matrix with the number of rows and columns equal to the out-degree π‘˜ and in-degree π‘˜ of the node, respectively. 𝜏 is the damping term acting on the outgoing edge state, and ⨂ denotes the multiplication of the corresponding position elements of the two vectors. When 𝜎 = 1, the outgoing edge state is affected by the external input 𝑒 . At this time, node 𝑣 is said to be the driver node. The node in the switch dynamics is like a switch device that receives the signal from the incoming edge and then processes and forwards it to the outgoing edge, and the processing and forwarding process is represented by the switching matrix in the node. Equation (1) can be rewritten as a linear time-invariant system as follows: π‘₯ = (π‘Š βˆ’ 𝑇)π‘₯ + 𝐻𝑒, (2) where π‘Š is the state matrix, which is the transpose matrix of the adjacency matrix of the line graph 𝐿(𝐺) from the directed graph 𝐺, 𝑀 β‰  0 if and only if the end node of edge 𝑗 is the start node of edge 𝑖, i.e., edge 𝑗 points to edge 𝑖. The nodes in the line graph 𝐿(𝐺) correspond to the edges in the original graph 𝐺, and the edges in the line graph 𝐿(𝐺) correspond to the pointing relationships between edges in the original graph 𝐺. 𝑇 is the damping matrix, which is a diagonal matrix with the damping terms corresponding to each edge on its diagonal elements. 𝐻 is the input matrix, which is a diagonal matrix whose 𝑖-th element is 𝜎 if and only if node 𝑣 is the starting node of edge 𝑖. It is worth noting that 𝑇 has no effect on the controllability of the edge dynamics in complex network and can be ignored in the discernment of controllability. In order to study the problems related to the controllability and observability of the edge dynamics in complex networks, we give the definitions of three node classifications and the related concepts of connected components. β€’ Divergent node. A node is said to be a divergent node if its out-degree is greater than its in-degree (π‘˜ > π‘˜ ). In particular, a node is said to be weakly divergent if its out-degree is greater than its in-degree by one (π‘˜ = π‘˜ + 1). β€’ Convergent node. A node is said to be convergent if its in-degree is greater than its out-degree (π‘˜ > π‘˜ ). In particular, a node is said to be weakly convergent if its in-degree is greater than its out-degree by one (π‘˜ = π‘˜ + 1). β€’ Balanced node. A node is said to be a balanced node if its out-degree is equal to its in-degree (π‘˜ = π‘˜ ). β€’ Connected components. The connected components can be divided into three categories. 1) Balanced components. Any node in the balanced component is the balanced node. 2) Unbalanced components. The unbalanced component contains one or more unbalanced nodes (π‘˜ β‰  π‘˜ ). 3) Isolated nodes. Nodes where the number of both outgoing and incoming edges are zero. The number and location of driver nodes required for controlling the edge dynamics in complex network are determined by the local structure of the nodes. When the edge dynamics of complex network is controllable, the divergent node is the driver node, and any one node in each balanced component is the driver node. The driver node needs to control its π‘˜ βˆ’ π‘˜ outgoing edges, and the driver node in each balanced component needs to control any one of its outgoing edges. The controlled outgoing edge is called the driven edge. From the principle of duality, it is known that when the edge dynamic is observable, the convergent node in the network is the sensor node, and any one node in the balanced component is the sensor node. The convergent node needs to observe its π‘˜ βˆ’ π‘˜ incoming edges, and the sensor node in the balanced component needs to observe any one of its incoming edges. The observed incoming edges are called the observed edges. 67 3. ROBUSTNESS We study the robustness based on the edge classification. Each edge is classified by the change in the number of driver nodes and sensor nodes when the edge is removed. Specifically, the number of driver nodes and sensor nodes are denoted by 𝑁 and 𝑁 , respectively. After an edge is removed, the number of driver nodes and sensor nodes in the remainder network is denoted by 𝑁 and 𝑁 , respectively. Edges can be classified into three categories: critical, redundant, and ordinary. The removal of a critical edge increases the number of driver nodes or sensor nodes, i.e., 𝑁 > 𝑁 or 𝑁 > 𝑁 . Conversely, the removal of a redundant edge decreases the number of driver nodes or sensor nodes, i.e., 𝑁 < 𝑁 or 𝑁 < 𝑁 . The rest edges are ordinary since removing them does not affect the number of driver nodes or sensor nodes. As an edge is removed, the in-degree of the target node (the termination node of this edge) and the out-degree of the source node (the starting node of this edge) decrease. Therefore, we can give an edge classification method based on the local structure of network. β€’ Critical edge. For an edge, if its source node is non-weakly divergent and its target node is balanced, the number of driver nodes increases after removing this edge, if its source node is balanced and its target node is non-weakly convergent, the number of sensor nodes increases after removing this edge. Therefore, the number of driver nodes or sensor nodes increases after removing a critical edge. It is worth noting that when both the source node and target node are balanced, removing the connecting edge between them will increase the number of driver nodes and sensor nodes at the same time. β€’ Redundant edge. For an edge, if its source node is weakly divergent and its target node is non- balanced, the number of driver nodes decreases after removing this edge, if its source node is non-balanced and its target node is weakly convergent, the number of sensor nodes decreases after removing this edge. Therefore, the number of driver nodes or sensor nodes decreases after removing a redundant edge. It is worth noting that when the source node is weakly divergent and the target node is weakly convergent, removing the edge between them will decrease the number of driver nodes and sensor nodes at the same time. β€’ Ordinary edges. Edges other than those mentioned above are ordinary edges. An example of the edge dynamics in complex network is shown in the Fig. 1. The nodes π‘₯ and π‘₯ are driver nodes, which need to receive external input signals. Similarly, the node π‘₯ is the sensor node, which needs to send observation signal to the outside. The nodes π‘₯ and π‘₯ are balanced nodes. According to our classification principle, the edge between π‘₯ and π‘₯ is the critical edge. When this edge is removed, π‘₯ becomes the sensor node and π‘₯ stays the same, leading to the number of sensor nodes in the network increases. The node π‘₯ is the convergent node and π‘₯ is the divergent node. According to our classification principle, the edge between π‘₯ and π‘₯ is the redundant edge. When this edge is removed, π‘₯ becomes the isolated node and π‘₯ stays the same, leading to the number of driver nodes in the network decreases. The edge between nodes π‘₯ and π‘₯ is an ordinary edge. In the following, we will apply the edge classification to model networks and derive the theoretical values. We will study the distribution of the edge classification in Erd π‘œ s–R 𝑒́ nyi (ER) networks, exponential (EX) networks and scale-free (SF) networks. We compare edge classification based on the structural controllability (traditional perspective) and based on the structural controllability and observability (new perspective) proposed in this paper in model networks. 68 Fig. 1. Edge classification. The network is controlled and observed by two input nodes and one output node respectively, i.e., 𝑒 , 𝑒 and 𝑦 . When removing a critical edge (π‘₯ β†’ π‘₯ , π‘₯ β†’ π‘₯ ), the number of driver nodes or sensor nodes increases. When removing a redundant edge (π‘₯ β†’ π‘₯ ), the number of driver nodes or sensor nodes decreases. Edge (π‘₯ β†’ π‘₯ ) other than those mentioned above is ordinary edge. We classify the edges in the network into critical edges, redundant edges and ordinary edges. As shown in Fig. 2, the trends of the percentages of the three edge classifications with average degree are extremely similar. The percentage of critical edges π‘š increases and then decreases as the average degree βŒ©π‘˜βŒͺ increases; the percentage of ordinary edges π‘š increases as the average degree βŒ©π‘˜βŒͺ increases; the percentage of redundant edges π‘š gradually decreases as the average degree βŒ©π‘˜βŒͺ increases. When the average degree is small, the number of edges in the network is small, and the vast majority of these edges are redundant edges, which means that the number of driver nodes or sensor nodes in the network will decrease after removing an edge. As shown in Fig. 2(a), we give a comparison of the edge classification between traditional perspective and new perspective in ER networks. Obviously, the proportion of critical edges and redundant edges in the new perspective classification method is higher than that in the traditional classification method, and the proportion of critical edges in the new method is nearly twice that in the traditional method. As shown in Fig. 2(b), there are very similar results in EX networks. In Fig. 2(c) and (d), we study the application of two classification perspective in SF with 𝛾 = 2.2 and 𝛾 = 3, respectively. It can be clearly found that the trend of the proportion of the three kinds of edges in the network is the same as that of the ER and EX networks. Furthermore, the proportions of the critical edge and the redundant edge when 𝛾 = 2.2 are significantly lower than that of the two kinds of edges when 𝛾 = 3. This means that different 𝛾 values will have a greater impact on the percentages of three edges. 4. THEORETICAL ANALYSIS The analytical results of the robustness depend on the degree distribution. The in- and out-degrees of model networks follow the same distribution, i.e., 𝑝(𝑖 ) = 𝑝(𝑖 ) = 𝑝(𝑖 ) . We give a general theoretical formulation of three edge classifications based on the structural controllability and observability. 69 Fig. 2. The edge classification in model networks. Comparison of edge classification from traditional (marked in square) and new perspectives (marked in circle) and their varies with the average degree βŒ©π‘˜βŒͺ in (a) the ER networks, (b) EX networks and SF networks with (c) 𝛾 = 2.2 and (d) 𝛾 = 3. ER, EX and SF networks are generated based on the static model [18,19,20] with 𝑁 = 5000. All data points and error bars are obtained by averaging over 10 independent realizations. π‘š =2 βˆ‘ 𝑝(𝑖) 𝑖 1 βˆ’ βˆ‘ 𝑝(𝑖)𝑝(𝑖 + 1)(𝑖 + 1) βˆ’ βˆ‘ 𝑝(𝑖) 𝑖 , (3) π‘š =2 1βˆ’ βˆ‘ 𝑝(𝑖) 𝑖 βˆ‘ 𝑝(𝑖)𝑝(𝑖 + 1)(𝑖 + 1) βˆ’ βˆ‘ 𝑝(𝑖)𝑝(𝑖 + 1)(𝑖 + 1) , (4) π‘š =1βˆ’π‘š βˆ’π‘š . (5) For ER networks, the average degree βŒ©π‘˜βŒͺ = βŒ©π‘˜ βŒͺ = βŒ©π‘˜ βŒͺ = 𝑀/𝑁, where 𝑁 and 𝑀 are the number of nodes and edges in the network, βŒ©π‘˜ βŒͺand βŒ©π‘˜ βŒͺ are the average out-degree and average in-degree, respectively. Both the out- and in-degree of the ER networks follow the Poisson distribution, i.e., 〈 βŒͺ 〈 βŒͺ 𝑝(𝑖) = . (6) ! According to the principle of classification of different edges, we obtain the expressions for the percentages of the three edges of the ER networks. 〈 βŒͺ 〈 βŒͺ 〈 βŒͺ π‘š = 2𝐼 (2βŒ©π‘˜βŒͺ)𝑒 1 βˆ’ 𝐼 (2βŒ©π‘˜βŒͺ)𝑒 βˆ’ 𝐼 (2βŒ©π‘˜βŒͺ)𝑒 , (7) 〈 βŒͺ where 𝐼 (π‘₯) is the modified Bessel function of first kind, 𝐼 (2βŒ©π‘˜βŒͺ) = βˆ‘ , 𝐼 (2βŒ©π‘˜βŒͺ) = !! 〈 βŒͺ βˆ‘ . !( )! 〈 βŒͺ 〈 βŒͺ 〈 βŒͺ π‘š = 2𝐼 (2βŒ©π‘˜βŒͺ)𝑒 1 βˆ’ 𝐼 (2βŒ©π‘˜βŒͺ)𝑒 βˆ’ 𝐼 (2βŒ©π‘˜βŒͺ)𝑒 , (8) π‘š =1βˆ’π‘š βˆ’π‘š . (9) Both the out- and in-degree of the EX networks follow the exponential distribution, i.e., ⁄ 𝑝(𝑖) = 𝐢𝑒 , (10) ⁄ where 𝐢 = 1 βˆ’ 𝑒 and πœ… = 1⁄ln ((1 + βŒ©π‘˜βŒͺ)/βŒ©π‘˜βŒͺ). 70 According to the principle of classification of different edges, we obtain the expressions for the percentages of the three edges of the EX networks. 〈 βŒͺ 〈 βŒͺ 〈 βŒͺ π‘š =( 〈 βŒͺ ) 1βˆ’( 〈 βŒͺ ) βˆ’ ( 〈 βŒͺ ) , (11) 〈 βŒͺ 〈 βŒͺ 〈 βŒͺ π‘š =2 1βˆ’( 〈 βŒͺ ) ( 〈 βŒͺ ) βˆ’ ( 〈 βŒͺ ) , (12) π‘š =1βˆ’π‘š βˆ’π‘š . (13) Both the out- and in-degree of the SF networks follow the power law distribution, i.e., 〈 βŒͺ( ) ⁄ ,〈 βŒͺ( ) 𝑝(𝑖) = ( ) , (14) where Ξ“(𝑠, π‘₯ ) is an incomplete Gamma function, Ξ“(𝑛) = (𝑛 βˆ’ 1)! is a Gamma function, and the parameters π‘Ž = 1⁄(𝛾 βˆ’ 1). According to the principle of classification of different edges, we obtain the expressions for the percentages of the three kinds of edges of the SF networks. π‘š = 〈 βŒͺ𝛿 βˆ‘ 𝑖Γ 1 βˆ’ 〈 βŒͺ𝛿 βˆ‘ (𝑖 + 1)Ξ“ Ξ“ βˆ’ 〈 βŒͺ 𝛿 βˆ‘ 𝑖Γ , (15) π‘š = 2 1βˆ’βŒ© βŒͺ𝛿 βˆ‘ 𝑖Γ 〈 βŒͺ 𝛿 βˆ‘ (𝑖 + 1)Ξ“ Ξ“ βˆ’ 〈 βŒͺ𝛿 βˆ‘ (𝑖 + 1)Ξ“ Ξ“ , (16) π‘š =1βˆ’π‘š βˆ’π‘š , (17) 〈 βŒͺ( ) ⁄ ,〈 βŒͺ( ) where 𝛿 = and Ξ“ = ( ) . 5. CONCLUSION For the study of the robustness of edge dynamics in complex networks, a traditional edge classification based on the structural controllability has been proposed in [16]. We innovatively offer a new edge classification from the structural controllability and observability perspective and develop a framework for studying the robustness. The general theoretical formulation of the edge classification in the edge dynamics of complex networks is derived. We apply the edge classification to the model networks, and find that the percentage of critical edges in the new classification is approximately twice as large as in the traditional classification. In future work, we will apply the new edge classification method to the real networks and give the corresponding theoretical formulation. In addition, the robustness of edges in switch networks will be our new research direction. ACKNOWLEDGMENT This work was supported by Youth Innovation Science and technology support plan of colleges in Shandong Province (2021KJ025). REFERENCES [1] B. BollobΓ‘s, Modern graph theory, Springer Science & Business Media1998. [2] R. Albert, A.-L. BarabΓ‘si, Statistical mechanics of complex networks, Reviews of modern physics, 74 (2002) 47. [3] M.E. Newman, The structure and function of complex networks, SIAM review, 45 (2003) 167-256. 71 [4] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, D.-U. Hwang, Complex networks: Structure and dynamics, Physics reports, 424 (2006) 175-308. [5] S.N. Dorogovtsev, A.V. Goltsev, J.F. Mendes, Critical phenomena in complex networks, Reviews of Modern Physics, 80 (2008) 1275. [6] M. Newman, Networks, Oxford university press2018. [7] R.E. Kalman, Mathematical description of linear dynamical systems, Journal of the Society for Industrial and Applied Mathematics, Series A: Control, 1 (1963) 152-192. [8] G. Menichetti, L. Dall’Asta, G. Bianconi, Network controllability is determined by the density of low in-degree and out-degree nodes, Physical review letters, 113 (2014) 078701. [9] Z. Yuan, C. Zhao, Z. Di, W.-X. Wang, Y.-C. Lai, Exact controllability of complex networks, Nature communications, 4 (2013) 1-9. [10] H. Yin, S. Zhang, Minimum structural controllability problems of complex networks, Physica A: Statistical Mechanics and its Applications, 443 (2016) 467-476. [11] C.-T. Lin, Structural controllability, IEEE Transactions on Automatic Control, 19 (1974) 201-208. [12] J Y.-Y. Liu, J.-J. Slotine, A.-L. BarabΓ‘si, Controllability of complex networks, nature, 473 (2011) 167-173. [13] M. Bohner, N. Wintz, Controllability and observability of time-invariant linear dynamic systems, Mathematica Bohemica, 137 (2012) 149-163. [14] Y.-Y. Liu, A.-L. BarabΓ‘si, Control principles of complex systems, Reviews of Modern Physics, 88 (2016) 035006. [15] Y.-Y. Liu, J.-J. Slotine, A.-L. BarabΓ‘si, Observability of complex systems, Proceedings of the National Academy of Sciences, 110 (2013) 2460-2465. [16] T. Nepusz, T. Vicsek, Controlling edge dynamics in complex networks, Nature Physics, 8 (2012) 568-573. [17] S.-P. Pang, W.-X. Wang, F. Hao, Y.-C. Lai, Universal framework for edge controllability of complex networks, Scientific reports, 7 (2017) 1-12. [18] F. Chung, L. Lu, Connected components in random graphs with given expected degree sequences, Annals of combinatorics, 6 (2002) 125-145. [19] K.-I. Goh, B. Kahng, D. Kim, Universal behavior of load distribution in scale-free networks, Physical review letters, 87 (2001) 278701. [20] M. Catanzaro, R. Pastor-Satorras, Analytic solution of a static scale-free network model, The European Physical Journal B-Condensed Matter and Complex Systems, 44 (2005) 241-248. 72