The dynamic processes on the edges of complex networks are closely related to various realworld 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.
In recent years, the node dynamics of 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.
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 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) of (2) = − ⨂ + , 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 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: 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 , graph , and the edges in the line graph () i.e., edge points to edge . The nodes in the line graph () correspond to the edges in the original 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 ( Isolated nodes. Nodes where the number of both outgoing and incoming edges are zero. ≠ ). 3)
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 − the sensor node in the balanced component needs to observe any one of its incoming edges. The observed incoming edges, and incoming edges are called the observed edges.
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 nonbalanced, 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–Ŕ 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. output node respectively, i.e., , and . When removing a critical edge ( → , number of driver nodes or sensor nodes increases. When removing a redundant edge ( → ), the → ), the number of driver nodes or sensor nodes decreases. Edge ( → ) other than those mentioned above is ordinary edge. three edges.
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 degree 〈〉 increases; the percentage of ordinary edges increases and then decreases as the average 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
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.
(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 [
= 2 ∑ ( ) 1 − ∑ ()( + 1)( + 1) − ∑ ( ) ,
For ER networks, the average degree 〈 〉 = 〈 〉 = 〈 〉 = / , where and are the number of respectively. Both the out- and in-degree of the ER networks follow the Poisson distribution, i.e., nodes and edges in the network, 〈 〉 and 〈
〉 are the average out-degree and average in-degree,
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〈 〉) 〈 〉 , where () is the modified Bessel function of first kind, (2〈 〉) = ∑ !! 〈 〉 , (2〈 〉) = ∑ 〈 〉 ! ( )! .
= 2 (2〈 〉) 〈 〉1 − (2〈 〉) 〈 〉 − (2〈 〉)
〈 〉 , (3) (4) (5) (6) (7) (8) (9) (10) percentages of the three edges of the EX networks.
=
〈 〉 ( 〈 〉 ) 1 −
〈 〉 ( 〈 〉 ) − ( 〈 〉 ) 〈 〉
, 〈 〉
〈 〉
, ,
Both the out- and in-degree of the SF networks follow the power law distribution, i.e., parameters = 1 ⁄( − 1 ). percentages of the three kinds of edges of the SF networks.
where Γ(, ) is an incomplete Gamma function, Γ( ) = ( − 1 )! is a Gamma function, and the According to the principle of classification of different edges, we obtain the expressions for the = 〈 〉 ∑ 1 − 〈 〉 ∑ ( + 1 )Γ Γ − 〈 〉 ∑ Γ , where = 〈 〉( ) and Γ = ⁄ ,〈 〉( ( ) )
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 [
Shandong Province (2021KJ025).
This work was supported by Youth Innovation Science and technology support plan of colleges in 74 (2002) 47. [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, [3] M.E. Newman, The structure and function of complex networks, SIAM review, 45 (2003) 167-256. (11) (12) (13) (14) (15) (16) (17)