{'fraction_non_alphanumeric': 0.05253574917843503, 'fraction_numerical': 0.009725552891020516, 'mean_word_length': 4.050235478806908, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Partial controllability of network dynamical systems with unilateral inputs

Our ability to control network dynamical systems is often hindered by constraints on the number and nature of the available control actions, which make controlling the whole network unfeasible. In this manuscript, we focus on the case where unilateral inputs are exerted on a subset of the network nodes. Leveraging the observation that, different from the case of subsystems, unilateral node reachability and controllability are equivalent, we provide conditions for a given node subset to be unilaterally controllable. The theoretical findings are then employed to develop a computationally efficient heuristic to select the nodes where the unilateral inputs should be injected


I. INTRODUCTION
Modeling, analyzing, and controlling network dynamical systems is of interest for applications as diverse as formation control [1], multicellular control in biology [2], [3], power systems [4], and financial market dynamics [5], [6]. In the last decades, control engineers have focused on designing distributed protocols capable of inducing the emergence of collective behaviors, such as e.g. consensus and synchronization [7]- [10]. More recently, the ambition to systematically tackle more general network control problems has brought to specify the classical concept of controllability to the case of network systems [11]. It has been pointed out that, when studying network dynamical systems, (i) controllability should be conferred through an appropriate choice of the nodes where the inputs should be injected, thereby several input selection algorithms have been developed [12], [13], (ii) existing controllability tests may be misleading since, when the number of inputs is much smaller than the number of network nodes, controlling a network can be energetically unfeasible [14]- [16], and (iii) achieving complete network controllability can turn out being unnecessary or unfeasible, and thus one should rather focus on controlling selected subnetworks [17].
When studying controllability, a crucial difference exists between large scale dynamical systems and network systems, whereby subsytem controllability differs from controllability of a node subset for a subtle, yet critical, aspect [18].
To the best of our knowledge, none of the existing work tackled the controllability problem of a subset of the network nodes with unilateral inputs, and this is the gap we aim at filling in this manuscript. Different from the case of unconstrained inputs, when the inputs are constrained to be unilateral, the controllability of a network cannot be studied through structural approaches, nor through the controllability gramian. This in turn restricts the theoretical tools available to design optimal input placement strategies, making the unilateral case much more challenging than the unconstrained case. We tackle this problem by first characterizing the convex cone containing the unilaterally controllable states of a linear dynamical system, which we show to differ from the one containing the unilaterally reachable states. Then, by means of a suitable projection, we translate these results for network systems, and obtain the conditions for unilateral reachability and controllability of a node subset that, different from the general case of systems, we observe to be equivalent. The theoretical findings are then used to develop a greedy heuristic to decide where to inject the unilateral inputs, which provides a suboptimal solution to the problem of maximizing the number of controllable nodes.

II. PRELIMINARIES
Given a set H, we denote by |H| its cardinality, and given a vector space, we denote by 0 its origin. Given a real vector space R n , we denote by R n ≥0 (R n ≤0 ) the set of vectors in R n with nonnegative (nonpositive) entries. Let D be a set of |D| = k vectors d 1 , . . . , d k in R n , Span(D) is the set of all linear combinations of the vectors in D. The positive span Span + (D) of D is the set of all linear combinations with nonnegative coefficients, that is, Span which constitutes a polyhedral convex cone [29]. If D is a singleton then Span + (D) is called a ray. All the rays and the singleton O = {0} are degenerate cones. Given a convex polyhedral cone C, we define its dimension |C| as the number of vectors required to generate it. The lineality space of a convex cone C is defined as the largest subspace X l := C ∩ −C contained in C, whose dimension is the lineality of C [30].
Next, let us denote by e i the i-th versor in R n . Given an index set K, we define X K as the subspace linearly spanned by ∪ i∈K {e i }. Furthermore, given a vector d ∈ R n , we denote by proj X K (d) = i∈K d T e i e i the orthogonal projection of d along X K . Given a complex vector c ∈ C n , we denote by (c) and (c) its real and imaginary parts, respectively. The operators ∨ and ∧ denote the logical disjunction and conjunction, respectively, whereas the symbol \ denotes a set difference. Finally, the big-O notation O(·) describes the order of magnitude of the algorithm execution time with respect to the number of steps required to complete it.

III. PROBLEM FORMULATION
Let us consider a linear dynamical network on a graph G = {V, E}, where V and E ⊆ (V × V) are the sets of its nodes and edges, respectively. Defining the network state x = [x 1 , . . . , x n ] T , with x i ∈ R being the state of the i-th node, the network dynamics are given bẏ where A ∈ R n×n is the adjacency matrix of G, whose ijth entry a ij = 0 if (i, j) ∈ E and a ij = 0 otherwise. Matrix A encapsulates both the individual dynamics and the interaction between the network nodes, which are encoded by the diagonal and off-diagonal elements of A, respectively. Matrix B ∈ R n×m is the input matrix, whose ij-th element modulates the effect the input u j has on the dynamics of node i. Here, we consider the case of unilateral inputs.
In what follows, without loss of generality, we consider only nonnegative inputs for the sake of clarity, whereby their sign will be determined by the sign of the entries of B. More formally, we make the following assumption.
for all t and each column of matrix B belongs to the set B = {e i , −e i , i = 1, . . . , n} [20].
Here, we focus on the case in which unilateral controllability of the whole network is not feasible, whereby the conditions given in [20] do not hold. The problem then arises of selecting the input so that the state of a subset of the network nodes can be steered towards any desired value. Before stating this problem, we need to define unilateral controllability of a node subset V s , whose associated state x s is the vector stacking the states of all nodes in V s .

Definition 2.
A node subset V s ⊆ V is unilaterally reachable if the state of its nodes x s can be steered from 0 to any target value in finite time through an appropriate selection of the unilateral input u(t).

Definition 3.
A node subset V s ⊆ V is unilaterally controllable if, for all initial conditions x s (0), the state of its nodes can be steered towards any target value in finite time through an appropriate selection of the unilateral input u(t).
Given the adjacency matrix A, the controllability problem we consider is that of designing the input matrix B fulfilling Assumption 1 that maximizes the cardinality of the set V s = V s (B) of unilaterally controllable nodes, that is, Solving (2) requires finding the conditions such that, given a set of control inputs, a set of nodes is unilaterally controllable, and then devising an input placement algorithm that finds a unilaterally controllable node subset of maximal dimension.

CONTROLLABILITY OF A NODE SUBSET
Let J be the Jordan normal form of matrix A and µ the number of its blocks. We associate to each Jordan block J i , whose size we denote by ν i , the corresponding eigenvalue λ i , for i = 1, . . . , µ. Next, let L := {l i,k , i = 1, . . . , µ, k = 1, . . . , ν i } be a set of µ chains of unit norm linearly independent (generalized) left eigenvectors of A with the maximal number of elements orthogonal to the columns of matrix B. Finally, let us denote by T the matrix obtained by juxtaposing row-wise the elements of L. We can now define the set γ i,k (l T i,k B) as for i = 1, . . . , µ. Additionally, we denote by C r (B) the positive span of the set of all γ i,k -s, that is, Theorem 1. If Assumption 1 holds, then (i) the cone C r (B) is the set of unilaterally reachable states of the pair (A, B); (ii) the lineality space X l of C r (B) is the largest unilaterally reachable subspace of the pair (A, B).
Proof. Statement (i): Let us consider the transformation z = T x. As J = T AT −1 , the dynamics of network (1) becomė z(t) = Jz(t) + T Bu(t). By setting z(0) = 0, we obtain its forced dynamics as Since x = T −1 z, and as the columns of T −1 are right generalized eigenvectors of A, z i,k (t) represents the dynamics along the right eigenvector r i,k of each Jordan block J i , for all i = 1, . . . , µ. Let us now distinguish the case in which r i,k is associated to a real or to a complex eigenvalue Case (a): (λ i ) = 0. From Assumption 1 (i.e., nonnegative inputs), we have that η j (u j ) ≥ 0 for all j. Hence, from (5) we have that As A is a real matrix, each complex eigenvalue will have a complex conjugate. Therefore, the modal dynamics associated to each of the ν i pairs of complex conjugate eigenvalues (λ i,k , λ * i,k ), k = 1, . . . , ν i occur along the plane X = Span({ (r i,k ), (r i,k )}) of R n and, according to Euler's formula, can be expressed as a sum of sinusoidal functions. Hence, all the states belonging to X are unilaterally reachable if there exists an index j such that proj X l T i,k b j = 0, ∀k ≥ k. If, instead, such an index did not exist, then no state would be unilaterally reachable. Finally, considering that (i) if two (or more) states are unilaterally reachable, then any positive combination of the these states is also unilaterally reachable, and (ii) any linear combination involving an unreachable state defines another unreachable state, Statement (i) follows. Statement (ii). From Statement (i), no state outside C r (B) is reachable. Therefore, Statement (ii) follows. Lemma 1. Let Assumption 2 hold, then the set of controllable states is C c (B) := X l (B) ∪ {x ∈ R n : exp(At)x ∈ C r (B)}.
Proof. The thesis follows from the consideration that a point x is controllable if and only if exp(At)x is reachable.

A. Node subset unilateral reachability
When studying partial unilateral controllability of network dynamical systems, we need to preserve the association between state variables and network nodes. Therefore, we now provide the following theorems and corollaries characterizing the unilateral reachability and controllability of a node subset.
Theorem 2. Given network (1) and a node subset V s ⊂ V, if Assumption 1 holds and proj X Vs (C r (B)) = X Vs , then V s is unilaterally reachable.
Proof. From Definition 2, for a node subset V s to be reachable, for allx s ∈ R |Vs| and x(0) : x s (0) = 0 there must exists a unilateral input u(t) that steers the network towards a statex such that the projection ofx on the subspace X Vs spanned by the versors {e i : i ∈ V s }, isx s . This is equivalent to the existence of a pointx ∈ C r (B) such that As from Theorem 1 C r (B) is the unilaterally reachable cone, and proj X Vs (C r (B)) = X Vs by hypothesis, a point x fulfilling (6) exists for allx s and x(0) : x s (0) = 0, and thus the thesis follows.
Interestingly, we note that the number of unilaterally reachable nodes may be larger than the dimension of the largest unilaterally reachable subspace.

B. Node subset unilateral controllability
Theorem 3. Given network (1), if Assumption 1 holds, then a node subset V s is unilaterally reachable if and only if it is unilaterally controllable.
Proof. Unilateral controllability of a node subset trivially implies its unilateral reachability, see Definitions 2 and 3. Hence, let us focus on proving that unilateral reachability of a node implies its unilateral controllability. From Definition 3, for a node subset V s to be unilaterally controllable, for allx s and x(0) there must exists a unilateral input u(t) that steers the network towards a statex such that the projection ofx on the subspace X Vs isx s . This is equivalent to the existence of a pointx ∈ C r (B) such that proj X Vsx =x s − proj X Vs exp(At)x(0).
As from Theorem 2 if V s is unilaterally reachable then proj X Vs C r (B) = X Vs , by hypothesis a pointx fulfilling (7) exists for allx s and x(0). Hence, V s is unilaterally controllable.
The equivalence between unilateral reachability and controllability of node subsets allows to derive a set of corollaries that characterize partial unilateral controllability of network systems. Corollary 1. Given network (1) and a node subset V s ⊆ V, if Assumption 1 holds and proj X Vs (C r (B)) = X Vs , then V s is unilaterally controllable.
Proof. Combining Theorems 2 and 3, the thesis follows.
Corollary 2. Let C r (B) be the unilaterally reachable set of the pair (A, B). There exists a controllable node subset V s such that |V s | ≥ |X l (B)|.
Proof. From Theorem 1 we know that if C r (B) is the unilaterally reachable set, this implies that X l (B) is its lineality space of dimension |X l (B)|. Moreover, considering that, for a given subspace X there always exists a set of indices K and the associated subspaceX = Span(∪ i∈K {e i }) such that projX X =X , this holds also for X = X l (B). Therefore, from Theorem 2 there exists a unilaterally reachable node subset V s of dimension at least equal to |V s | = |X l (B)| that, from Theorem (3), is also unilaterally controllable.
The next corollary provides a sufficient condition guaranteeing that there exists a unilaterally controllable node subset V s that contains a given node i.
Corollary 3. Given a node, say i, if there exists a quadruplet {h, j, k, m} such that r T j,k e i > 0, r T m,h e i < 0, and {r j,k , r m,h } ∈ C r (B), then there exists a unilaterally controllable node subset V s such that i ∈ V s . Proof. Considering that proj ei C r (B) = e i , the thesis follows from Corollary 1.

Remark 1.
The mathematical treatment of this section substantially differs from the analyses that are performed when seeking complete unilateral controllability [20]. First, when the network is not completely unilaterally controllable, the set of reachable states is a convex cone instead of a vector space. Second, we needed to show and consider that, albeit the set of reachable states differs from that of controllable states (Lemma 1), the reachable and controllable node subsets do coincide (Theorem 3). Finally, we had to account for the fact that the number of unilaterally reachable nodes can be larger than the maximal dimension of a unilaterally reachable subspace, as remarked after Theorem 2.

V. GREEDY ALGORITHM
In what follows, we shall leverage the theoretical findings of Section IV to design a heuristic for solving problem (2). Before illustrating the derivation of the algorithm, we need to introduce the spanning set W(B) of the lineality space X l (B) ∈ C r (B) , which can be computed as (8) where i=1, . . . , µ, k=1, . . . , v i . Furthermore, let S be the set of all subspaces of R n such that proj X C r (B)=X , ∀X ∈S.
From Theorem 1, solving problem (2), that is, finding a maximal unilaterally controllable node subset, is equivalent to finding the matrix B that maximizes the cardinality of the largest subspace in S. Namely, Unfortunately, (9) is a combinatorial problem with time computational complexity of order O(n!) that can only be solved through extensive search, which is unfeasible even for a network of a handful of nodes.
Since finding an exact solution of (9) is typically unfeasible, we propose a two-step procedure for the selection of matrix B whose computational complexity is determined by that of finding the Jordan form J, that is, O(n 4 ). In Step 1, we seek for a heuristic approach that tries to maximize the lineality |X l (B)|, which from Corollary 2 is a lower bound for the cardinality |V s | of the unilaterally controllable node subset V s . Then, Step 2 attempts to add to V s the nodes fulfilling the sufficient condition for node unilateral controllability given in Corollary 3.
Here, we seek for the suboptimal solution to problem (9). The heuristic we propose (Step 1) takes as inputs the matrix A and the number of available inputs m. Denoting B k the B selected at the k-th iteration, the algorithm starts with B 0 =0 n×m . Then, at each iteration, one or two columns are added to B. Defining ∆(β):= |X l ([B k−1 , β])| − |X l (B k−1 )|, where β∈B, we can now distinguish two different cases: 1) If there exists β∈B such that ∆(β)>0, a single column is added at step k, that is, 2) If, instead, a β∈B such that ∆(β)>0 does not exist, we add two columns to B k−1 at step k, that is, Summing up, at each step k our updating rule attempts to add the input that maximizes the lineality |X l (B k )|. When such an input is not unique, it selects the input that adds the largest number of rays in C r (B k ). If instead we cannot find a β such that ∆(β) is positive, then we add the two inputs that maximize |X l (B k )|. The algorithm stops when B k ∈R n×m . Note that this first step has a computational complexity of O(n 4 ), due to the evaluation of the Jordan form of A.
Once we have computed B=B m , we need to identify one of the unilaterally controllable node subsets V 1 s corresponding to B. To this aim, we leverage Corollary 2, which states that there exists a unilaterally controllable node subset To identify such a node subset, we compute the set W( B) according to (8). Then, we build the set V 1 s so that the elements of the sets V 1 s and W( B) can be associated into |V 1 s | pairs (v j , w i ) such that (i) no pairs share a common element and (ii) each pair (v j , w i ) is such that e T vj w i =0. Finding this association can be recast as the problem of finding the maximum matching [31] of an unbalanced bipartite graph Here, V b :=V w ∪ V s is the set of vertexes and each node in V w represents an element of W( B). The set of edges E b ={(i, j)|e T i w j =0 ∧ w j ∈W( B)} defines all the possible associations, by appriopriately connecting the nodes in V w to those in V s . Finding a maximum matching is possible by means of the Hopcroft-Karp algorithm [32] and thus the computational complexity of this sub-step is Step 2. Enlarging the unilaterally controllable node subset.
In the second step, we enrich the unilaterally controllable node subset V 1 s by exploiting the set C r ( B) \ X l ( B). To do so, let us define the set whose positive span is C r ( B)\X l ( B). Then, let us define the matrix Q as the matrix obtained by juxtaposing the elements Step 1 Maximizing the lineality |X l (B)|.
compute β as in (12)  of Q( B) column-wise. Exploiting Corollary 3, we then add a node to V 1 s whenever the i-th row of Q encompasses two nonzero entries, say q ij and q im , that are such that sgn(q ij )= − sgn(q im ). Let us note that the computational complexity of this step of the algorithm is O(n 3 ).
Step 2 Enlarging the unilaterally controllable node subset associated to B Inputs: Q, V 1 s for i = 1, . . . , n do if ∃ l, m:sgn(q i,m )=− sgn(q i,l ) then Set V 1 s =V 1 s ∪ {i} Remove the l-th and m-th columns from Q end if end for Output: V s =V 1 s .

Application on a sample network
To illustrate our heuristic, we consider a linear network dynamical system on the graph G depicted in Fig. 1, whose dynamics is described by matrix with spectrum {4, 3, 0, 1 + 4i, 1 − 4i, 2 + 3i, 2 − 3i}. Let us assume that we can inject m=2 unilateral controls. The input matrix B is designed following Step 1, that is, by maximizing the lineality |X l ( B)|. At time instant k=1, four possible selections of β (e 2 , e 6 , −e 2 and −e 6 ) yield the same (positive) ∆(β). Hence, β should be selected among these four according to (11b). However, since all choices would yield the same |C(B 1 )|, the selection is performed randomly, and we elect B 1 =−e 6 , with the set W(B 1 ) being [r 6 , r 7 ]. At k=2, −e 2 is the unique β returning ∆(β)>0. Hence, we select node 2 as the second and last node where a control signal is injected, i.e., we set B=B 2 =[−e 6 ; −e 2 ] and W( B)=[r 1 , r 4 , r 5 , r 6 , r 7 ].
Having selected the matrix B, we now turn to finding one of the possibly multiple unilaterally controllable node subsets V 1 s such that |V 1 s |=|X l ( B)| by solving the maximum matching problem. Among the multiple equivalent solutions to this problem, we randomly pick V 1 s ={v 1 , v 2 , v 4 , v 5 , v 6 }. Finally, we compute, from (13), Q( B)={−r 2 , r 3 }, and from Step 2 of the proposed heuristic we can enlarge the unilaterally controllable node subset with node 3, that is V s = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 }. Interestingly, in this simple example, we find that |V s |>|X l |, that is, the number of unilaterally controllable nodes is greater than the largest unilaterally controllable subspace.

VI. CONCLUSIONS
In this letter, we have studied controllability of linear network dynamical systems when the inputs are unilateral. Specifically, we focused on the case where the constraint on the number and type of inputs prevents the achievement of complete controllability of the network system, whereby only a node subset can be made controllable. In this setting, we have identified conditions for unilateral reachability and controllability of a node set, which we found to be equivalent, different from the general case of subsystems, where we have proved that reachability does not imply controllability. After showing that maximizing the size of a controllable nodes subset is a combinatorial problem, we have leveraged the theoretical findings on unilateral controllability to build an heuristic that can find a suboptimal solution to this problem in polynomial time, as illustrated on a sample network.
Our work has laid the foundations of partial controllability under unilateral inputs, thus paving the ways for future studies in this area of research. First, alternative heuristic approaches may be developed and tested against the one proposed in this manuscript. Moreover, once partial controllability has been guaranteed, the problem of evaluating the energy associated to the control action arises, thereby minimum energy control problems could be formulated in this setting.