# Target control based on edge dynamics in complex networks

#### ByAUTHOR

Jun 19, 2020

In the real world, the dynamical processes performed in the vast majority of systems are nonlinear. However, we can not understand the dynamics of many complex systems deeply, such as the neural network of the human brain. Thus, before exploring the dynamical rules in a nonlinear system, it is essential to lucubrate the dynamics of linear systems, as they are the basis of solving the nonlinear problems. Here, we will firstly introduce the linear time-invariant(LTI) system:

$${begin{array}{ccc}dot{x} & = & Ax+Bu,\ y & = & Cx,end{array}$$

(1)

where (xin {R}^{N},yin {R}^{S}) and (uin {R}^{M}) are the state vector, output vector and control inputs, respectively. (Ain {R}^{Ntimes N},Bin {R}^{Ntimes M}) and (Cin {R}^{Stimes N}) represent the transposed matrix of the coupled matrix, the input matrix and the output matrix, respectively. The simplified representation of the above LTI system is ((A,B,C)). Here, dim((C)) denotes the dimension of the subspace (C), through which we simplify the dimension of system as ((A,B,C)) (e.g., (dim(A,B,C)) is denoted as (d(A,B,C))).

Generally, the target controllability can be regarded as the output controllability of the LTI system. Hence, we give the following definition and theorem.

### Definition 1

(output controllability)18 A system is output controllable if we can move its output from any initial state to any desirable state in a finite time interval with an appropriate input. The LTI system ((A,B,C)) is output controllable if and only if its output controllability matrix has full rank:

$$d(A,B,C)=rank[C(B,AB,{A}^{2}B,ldots ,{A}^{N-1}B)]=Smathrm{}.$$

(2)

Here, the target edges can be seen as C, A and B are the matrices given by Eq. (1).

Let (G(V;E)) denote a network, (V) denote the node set and (E) denote the edge set. The numbers of nodes and edges are denoted by (N) and (M), respectively. (X=[{x}_{1},{x}_{2},cdot cdot cdot ,{x}_{{rm{M}}}]) denotes the state vector of each edge, which can be viewed as the packages on a router network or the loads on a line in a power network. ({y}_{{rm{v}}}^{+}) and ({y}_{{rm{v}}}^{-}) denote the states of the inbound edges and outbound edges of vertex (v), respectively. Generally, the states of the outbound edges ({y}_{{rm{v}}}^{+}) are affected by the states of the inbound edges ({y}_{{rm{v}}}^{-}), the losses of inbound edges ({tau }_{{rm{v}}}otimes {{y}_{{rm{v}}}}^{+}(t)) and the external disturbance on the corresponding nodes ({sigma }_{{rm{i}}}{u}_{{rm{i}}}(t)). ({M}_{{rm{v}}}) is a switching matrix that denotes the adjacency relationship between the inbound edges and the outbound edges.

The equation of the switchboard dynamic process13 is as follows:

$${dot{{y}_{{rm{v}}}}}^{+}({rm{t}})={M}_{{rm{v}}}{y}_{{rm{v}}}^{-}({rm{t}})-{tau }_{v}otimes {{y}_{{rm{v}}}}^{+}({rm{t}})+{sigma }_{{rm{i}}}{u}_{{rm{i}}}({rm{t}}),$$

(3)

where ({sigma }_{i}) is 1 if vertex i is a driver node and zero otherwise, and (otimes ) denotes the entry-wise product of two vectors of the same size.

Here, Eq. (1) can be rewritten in terms of ({x}_{{rm{i}}}). The connection of the switchboard dynamic and a standard linear dynamical system can be rewritten in terms of ({x}_{{rm{i}}}) as

$$dot{X}=(W-T)X+Hu,$$

(4)

where (W=[{w}_{{rm{kj}}}]) and ({w}_{{rm{kj}}}) may be nonzero if and only if the head of edge ({e}_{{rm{k}}}) is the tail of edge ({e}_{{rm{j}}}). (Tin {R}^{Mtimes M}) is a diagonal matrix with the damping term on the main diagonal. (H) is a diagonal matrix where the (i) th diagonal element ({sigma }_{i}) is the tail of the (i) th edge. Furthermore, Eq. (4) can be rewritten in a linear time-invariant dynamical form (dot{X}=AX+Bu) with (A=W-T) and (B=H). In fact, (W) is the adjacency matrix of the linear graph (L(G)) on the original graph (G). The nodes of (L(G)) are the edges of (G), and the edge ({e}_{{rm{i}}{rm{j}}}^{{rm{{prime} }}}) of (L(G)) indicates that the head of edge ({e}_{{rm{i}}}) is the tail of edge ({e}_{{rm{j}}}).

According to the exact controllability, the damping matrix (T) with identical diagonal elements has no effect on the edge controllability of the network characterized by (W-T)14. However, if the diagonal elements are nonzero, the system can be controlled by only one driver node according to the theory of structural controllability5. Except in the above two cases, we need to account for the influence of matrix (T) on the controllability. The main results of the switchboard dynamics are as follows13.

The minimum set of driver nodes required to maintain the structural controllability of the switchboard dynamics on a network (G(V,E)) is determined by selecting the divergent vertices of G and one arbitrary vertex from each balanced component. The divergent node (v) is the node with ({d}_{{rm{v}}}^{-} < {d}_{{rm{v}}}^{+}), and the balanced component is the component such that each node satisfies ({d}_{{rm{v}}}^{+}={d}_{{rm{v}}}^{-}). For vertex (v), ({d}_{{rm{v}}}^{+}) is the out-degree and ({d}_{{rm{v}}}^{-}) is the in-degree. In addition, ({M}_{{rm{D}}}) is the minimum of the driven edges. Then, we have

$${M}_{{rm{D}}}=mathop{sum }limits_{{rm{i}}mathrm{=1}}^{N}max({d}_{{rm{i}}}^{+}-{d}_{{rm{i}}}^{-}mathrm{,0)}+mathop{sum }limits_{{rm{i}}mathrm{=1}}^{c}{beta }_{{rm{i}}}mathrm{}.$$

(5)

here, N is the number of vertexes, c is the number of connected components and ({beta }_{{rm{i}}}) is 1 if the (i) th connected component is balanced and zero otherwise.

Given a directed network (G(V,E)) where |V| = N and (|E|=L) denote the number of vertexes and edges, if ({a}_{{rm{ji}}}ne 0) is in the matrix (A), then there is a link from node (i) to node (j). A set of target edges with size S may be denoted as ({{c}_{1},{c}_{2}mathrm{,…,}{c}_{{rm{S}}}}). The target edges may also be denoted as ({{e}_{1},{e}_{2},ldots ,{e}_{{rm{S}}}}). In the switchboard dynamics, the controllability of the target edges is equivalent to the controllability of the corresponding nodes in the linear graph (L(G)); the linear graph is a graph where we view the edge in the original graph G as a node, and two edges are connected when the head of an edge is the tail of the other edge. Formula (y=Cx) is the state of the target edges ({x}_{{{rm{c}}}_{1}},{x}_{{{rm{c}}}_{2}},,mathrm{…,},{x}_{{{rm{c}}}_{{rm{S}}}}). Similar to the conclusion in ref. 11, the target edge controllability can also be regarded as a special output controllability problem on the linear graph.

For a directed network (G) with the adjacency matrix of its linear graph: A = [({a}_{{rm{ij}}})], ({a}_{{rm{ij}}}) = 1 if there is a link (({e}_{{rm{i}}},{e}_{{rm{j}}})) and 0 otherwise.

### Definition 2

(Edge distance) The distance between two edges is the number of internal nodes on a path that connects the two edges, and it is denoted by d′.

This definition is used in the k-travel theory, and it differs from the distance between two nodes, which is shown in Fig. 1.

We have ({d}_{{rm{ij}}}^{,{prime} }=k) if the ((i,j)) entry of matrix ({A}^{k}) is nonzero. For general directed networks, ({d}_{{rm{ij}}}^{,{prime} }) could have multiple values because there could be many different walks connecting edge (i) and edge (j). For a directed tree, all of the paths are unique. Consequently, ({d}_{{rm{ij}}}^{,{prime} }) is single-valued for any edge pair ((i,j)) in (T). To clarify algorithm 1, we first introduce several definitions:

### Definition 3

(Structurally equivalent). Two matrices (A=({a}_{{rm{i}}j})) and (tilde{A}=({tilde{a}}_{{rm{i}}j})) with the same size are said to be structurally equivalent if the entries of (A) being nonzero implies that entries in the corresponding location of (tilde{A}) are also nonzero5. Moreover, if any entries in (A) are zeros, the corresponding entry (tilde{A}) must also be zero, which is applicable for the structurally equivalence of systems ((A,B,C)) and ((tilde{A},tilde{B},tilde{C})).

### Definition 4

(Generic dimension)19. The generic dimension (gd(A,B,C)) of the output state space is defined by

$$gd(A,B,C)=mathop{{rm{max }}}limits_{tilde{A},tilde{B},tilde{C}}rank(tilde{A},tilde{B},tilde{C}),$$

(6)

where (tilde{A},tilde{B},tilde{C}) are structural equivalent to (A,B,C), respectively. The generic dimension is used to describe the control range of the edge. Based on the switchboard dynamics, we use this k-travel theory to give an effective algorithm to find the controllable set of any edge in the directed tree, especially the root edge.

### Theorem 1

(k-travel theory) For a directed tree, we can control the target edges set ({ {mathcal L} }_{{rm{i}}}={{e}_{{{rm{i}}}_{1}},{e}_{{{rm{i}}}_{2}},,mathrm{…,},{e}_{{{rm{i}}}_{{L}_{i}}}}) by controlling an edge ({e}_{{rm{i}}}) provided that ({d}_{{rm{ik}}}^{{prime} }) (the distance from edge ({e}_{{rm{i}}}) to edge ({e}_{{rm{k}}})) meets ({d}_{{rm{ik}}}^{{prime} }=k-1) for every integer (kin mathrm{[1,}{L}_{{rm{i}}}]).

### Proof:

In switchboard dynamics, Eq. (2) can be written in a linear time-invariant dynamical form (dot{X}=AX+Bu), where (A) is the adjacency matrix of the linear graph (L(G)) of the original graph (G). The nodes of (L(G)) denote the edges of (G), and the edge ({e{prime} }_{{rm{ij}}}) of (L(G)) indicates that the head of edge ({e}_{{rm{i}}}) is the tail of edge ({e}_{{rm{j}}}).

According to the output controllability theorem, edge ei can control all of the edges in ( {mathcal L} )i if the generic dimension of the matrix ( {mathcal L} ={l}_{i,alpha }[{b}_{{rm{i}}},A{b}_{i},{A}^{2}{b}_{{rm{i}}},,mathrm{…,},{A}^{N-1}{b}_{{rm{i}}}]) is ({L}_{{rm{i}}}), i.e., if

$$gd( {mathcal L} )=gd({l}_{{rm{i}},alpha }[{b}_{{rm{i}}},A{b}_{{rm{i}}},{A}^{2}{b}_{{rm{i}}},ldots ,{A}^{N-1}{b}_{{rm{i}}}])={L}_{{rm{i}}},$$

(7)

where ({l}_{{rm{i}},alpha }=I({{i}_{1},{i}_{2},,mathrm{…,},{i}_{{{rm{L}}}_{i}}})) represents an ({L}_{{rm{i}}}times M) matrix that contains the ({{i}_{1},{i}_{2},,mathrm{…,},{i}_{{{rm{L}}}_{{rm{i}}}}}) th rows of the identity matrix (I). Moreover, ({b}_{{rm{i}}}) is the (i) th column of the identity matrix. Here, M denotes the number of edges in (G), and ({{i}_{1},{i}_{2},,mathrm{…,},{i}_{{{rm{L}}}_{{rm{i}}}}}) are the corresponding indices of the edges set ( {mathcal L} )i in L(G). The (Mtimes 1) vector ({A}^{k}{b}_{{rm{i}}}) contains nonzero entries corresponding to those edges with ({d}_{{rm{ij}}}^{{prime} }=k); i.e., the distance between edge ei and ({e}_{{rm{j}}}) is (k) in (G).

Given a directed-tree network, there is only one edge in ({ {mathcal L} }_{{rm{i}}}) that satisfies ({d}_{{rm{ij}}}^{{prime} }=k), which is assumed to be ({e}_{{rm{k}}}) with index ({i}_{{rm{k}}}) in (L(G)). Thus, We have ({l}_{{rm{i}},alpha }{A}^{k}{b}_{{rm{i}}}={beta }_{{rm{k}}}{I}_{{i}_{{rm{k}}}}), where ({beta }_{{rm{k}}}) is a nonzero constant. ({I}_{{{rm{i}}}_{{rm{k}}}}) is the ({i}_{{rm{k}}}) th column in the identity matrix. Hence, we have

$$gd( {mathcal L} )=gd[{beta }_{1}{I}_{{{rm{i}}}_{1}},{beta }_{2}{I}_{{{rm{i}}}_{2}}mathrm{,…,}{beta }_{{L}_{{rm{i}}}}{I}_{{{rm{i}}}_{{L}_{i}}}].$$

(8)

Since ({I}_{{{rm{i}}}_{1}},{I}_{{{rm{i}}}_{2}},,mathrm{…,},{I}_{{{rm{i}}}_{{L}_{i}}}) are independent, (gd( {mathcal L} )={L}_{{rm{i}}}). According to the output controllability theorem, we can control the the edges in ( {mathcal L} )i by controlling the edge ({e}_{i}).

Based on the above theorem, we can find the set of edges controlled by edge ({e}_{{rm{i}}}) in a directed tree. Figure 2 shows that two driven edges are required to control the target edges under the SBD theory, and k-travel theory requires only one such edge.

In SBD theory, to control all of the edges, the minimum number of driver nodes and driven edges can easily be obtained by checking the in-degree and out-degree of each node.

For the problem of a single edge input, we propose a k-travel theory based on the edge dynamics. Our theory shows that by controlling one edge, we can control a set of target edges given that the lengths from the driven edge to the rest of the target edges are different from each other. We verify that the approach based on k-travel theory is more efficient than the traditional edge dynamics method because it can control more edges according to output controllability theory (Lemma 1).

Although the method based on k-travel theory is efficiently control tree-like networks with single driven edge (which is shown in Fig. 2), the situation becomes more complex in real networks. For more general cases, we present an iterative algorithm to approximate the minimum number of driven edges and driver nodes. We can prove that the driven edges and driver nodes obtained by our algorithm can control the target edges. This algorithm is based on the k-travel theory, and we call it the TEC (target edge control) algorithm (it is shown in Fig. 3a–e).

The main processes of the TEC algorithm are shown in Fig. 3, and they are based on structural control theory5,6 as well as the edge dynamics13. Step 1: We are given a directed network (G) with target edges(the red lines). Step 2: We construct a bi-layer bipartite graph, locate the head nodes of the target edges in the right part, and find these edges’ tail nodes in the left part. Then, we add the edges which points to the tail nodes of the target edges in graph (G), and we construct another bipartite graph with the tail nodes of the new edges in the left part such that the right part contains their head nodes. Step 3: We use the greedy algorithm for target edges control. In the first iteration, for the tail node of each target edge, if the in_degrees of the middle nodes are not less than their corresponding out_degrees, we select the same number of in_edges. Otherwise, the extra target edges are the driven edges ({E}_{{rm{t}}}), and the driver nodes are the tail nodes of ({E}_{{rm{t}}}), which are denoted by ({D}_{{rm{t}}}). The set of total driven edges is (E=Ecup {E}_{{rm{t}}}), with tail nodes (D=Dcup {D}_{{rm{t}}}). Step 4: In the next iteration, the edges reserved in the left part of the bi-layer bipartite graph are the new target edges in the second iteration. If there is still an edge pointing to the tail nodes of the target edges, go back to step 2 . If not, stop. Step 5: By controlling the driver nodes calculated from the TEC, we can control the driven edges and then all of the targets can be controlled. In the above control process, the target edges or nodes are controlled in some chronological order. The process is given in the pseudo-code in the following table.

Here, ({d}_{{{rm{G}}}_{L}})(v) means the degree of vertex v in graph ({G}_{{rm{L}}}). In each iteration, the times required to calculate the driver nodes and the driven edges are (O(N)), and the depth of iteration is (N) at most. Therefore, the complexity of the TEC algorithm is (O({N}^{2})).