Partial containment control over signed graphs
Pietro DeLellis Anna DiMeglio Franco Garofalo Francesco Lo Iudice

Smoothed finite element method for stress intensity factor estimation: benefits and limitations
    Rokach I.V.myfootnote
    Received XX XXXX XXXX / Accepted XX XXXX XXXX
===============================================================================================




In this paper, we deal with the containment control problem in presence of antagonistic interactions. In particular, we focus on the cases in which it is not possible to contain the entire network due to a constrained number of control signals. In this scenario, we study the problem of selecting the nodes where control signals have to be injected to maximize the number of contained nodes. Leveraging graph condensations, we find a suboptimal and computationally efficient solution to this problem, which can be implemented by solving an integer linear problem. The effectiveness of the selection strategy is illustrated through representative simulations.









§ INTRODUCTION

The problem of coordinating the dynamics of ensembles of agents connected through static or dynamic network topologies has been deeply investigated in the last decades. In particular, departing from the pioneering work of DeGroot in the Seventies <cit.>, substantial research effort has been devoted to unravel the mechanisms leading to the emergence of consensus in networks of simple integrators. The problem has
been thoroguhly studied both in continuous and discrete time <cit.>, on undirected or directed graphs, and in presence of delays <cit.>. 
Consensus has been also investigated in a
leader-following setting, in which one node, the leader, drives a network of linear systems towards a desired value <cit.>.
Achieving consensus is not the only possible control goal in multi-agent systems. Indeed, in applications of networks of autonomous agents, the objective is often to contain a group of agents within a certain area, e.g. not to enter populated areas. Motivated by that, Ji and coworkers introduced the so-called containment control problem, where multiple leaders have to drive a group of mobile agents within a desired convex polytope <cit.>. Later works have further analyzed this problem to account for the presence of directed interactions <cit.>, possible switches in the network topology <cit.>, uncertainty <cit.>, and higher-order dynamics <cit.>.

As noted by Altafini in <cit.>, most of the works on consensus and containment control relies on the assumption of cooperation among the agents in the system, as all the network edges are assumed to have positive weights. However, in social network theory, besides cooperative interactions, also antagonism is commonly observed <cit.>. A natural setting to describe such interactions is to characterize the network topology through the so-called signed graphs, introduced in the Fifties by Harary <cit.> to model the
disliking, indifference, and liking sentiments described by psychologists in social interactions. These considerations motivated a bulk of studies on consensus and containment control over signed graphs <cit.>. In particular, in <cit.> the author showed that when the graph is balanced, bipartite consensus can be achieved, that is, the states of all the agents will have the same modulus, but possibly different signs. These results were later extended to the case of non-strongly connected graphs and discrete-time dynamics <cit.>.  


Recently, a first definition of containment control over signed graphs was given in <cit.>. Specifically, the author says that a network is contained when the states of its nodes converge towards the convex hull spanned by the leaders and by their symmetric trajectories. Assuming continuous-time dynamics, conditions guaranteeing the achievement of full network containment were achieved. Similar results were obtaibed in <cit.> for the case of generic linear heterogeneous node dynamics. 

However, in large directed networks where the number of control signals is constrained, it is seldom possible to contain the whole network, as it would require to directly inject a control input in every root strongly connected component (RSCC) of the network. Therefore, 
in this paper, we formulate the partial containment control problem over signed graphs. When the number of control inputs is limited, our goal is to maximize the number of nodes we asymptotically contain. Exploiting two graph condensations, we first derive sufficient conditions to contain the atom of our network, that is, a SCC, and then devise a suboptimal algorithm to efficiently deploy the control inputs. Interestingly, this strategy only relies on information on the network topology and not on the initial state of the nodes, which might be non-accessible. Moreover, we illustrate how the algorithm can be translated into an integer linear program, and we illustrate its effectiveness on a representative numerical testbed.



§ MATHEMATICAL PRELIMINARIES



 §.§ Signed graphs

A directed signed graph 𝒢 consists of an unsigned directed graph 𝒰={𝒱,ℰ} and a partial mapping σ:ℰ→{+,-}<cit.>. An edge (i,j)∈ℰ is called positive if σ(i,j)={+}, while it is called negative otherwise.
We associate to 𝒢 a weighted adjacency matrix A, whose ij-th element a_ij is positive if (i,j) ∈ℰσ(i,j)={+}, negative if (i,j) ∈ℰσ(i,j)={-}, and zero otherwise.

Throughout the manuscript, we shall consider signed graphs fulfilling the following assumption.

| a_ii|>0 and ∑_j=1^n |a_ij|=1, for all i=1,…,n. 


A directed signed graph 𝒢 is structurally balanced if there exists a bipartition {𝒱^1, 𝒱^2} of 𝒱, 
such that a_ij≥ 0, for all (i,j)∈𝒱^θ and a_ij≤ 0 for all (i∈𝒱^θ , j∈𝒱∖𝒱^θ), for all θ∈{1,2}. 𝒢 is unbalanced otherwise.

Notice that every unsigned graph is structurally balanced with 𝒱^1=𝒱 and 𝒱^2=∅.

Following <cit.> and <cit.>, we define the enlarged graph associated to 𝒢 as follows:






The enlarged graph 𝒢={𝒱,ℰ} associated to 𝒢 is a (unsigned) directed graph of 2n nodes (𝒱={1,…,n,1^-,…,n^- }) and all positive edges related to that of 𝒢 through the adjacency matrix A, whose elements are 

    ã_ij= ã_i+N,j+N=   max (0,a_ij)≥ 0,
    ã_i+N,j=ã_i,j+N=   max(0, -a_ij) ≥ 0,

for i,j=1,…,N.




 §.§ Some useful lemmata


Let us consider a reducible matrix in normal form:

    M=[ [ M_1   0   0   0;   ⋮   ⋱   ⋱   ⋮;   0   ⋯ M_q   0; R_1   ⋯ R_q   S ]],

where M_j, j=1,…,q, are semi-convergent irreducible matrices and S is a convergent matrix. We then have

    lim_k→+∞M^k=[ [ M_1^∞     0     0     0;     ⋮     ⋱     ⋱     ⋮;     0     ⋯ M_q^∞     0;     ⋯ R^*_j     ⋯     0 ]],

where M_j^∞=lim_k→+∞M_j^k and R^*_j=(I-S)^-1 R_j M_j^∞. Furthermore, if λ=1 is an eigenvalue of M_j, then M_j^∞=ψ_jξ_j^T, where ξ_j and ψ_j are the left and right eigenvectors associated to λ=1, respectively, scaled so that ξ_j^Tψ_j=1. 


<cit.> Given a strongly connected signed graph 𝒢 and its associated enlarged graph 𝒢, 
𝒢 is structurally balanced if and only if 𝒢 is disconnected and composed of two strongly connected components.


<cit.> Given a strongly connected signed graph 𝒢 and its associated enlarged graph 𝒢, 𝒢 is structurally unbalanced if and only if 𝒢 is strongly connected.



 §.§ Graph condensations


Given any pair of vertex sets {𝒱,𝒱'}, with |𝒱|≥|𝒱'|, any (single-valued) function f:𝒱→𝒱' is called a condensing function. Moreover,

    𝒱_i:={ t∈𝒱:f(t)=i },   i∈𝒱'.



Let us consider a graph 𝒢 = (𝒱,ℰ), a vertex set 𝒱', a condensing function f:𝒱→𝒱', and the edge set ℰ'={(i∈𝒱',j∈𝒱'),i j|∃(t,u)∈ℰ |f(t)=i,f(u)=j }. The graph 𝒢'={𝒱',ℰ'} is the condensation of 𝒢 induced by f.



The classic condensation 𝒢^c of a graph 𝒢 is the condensation of 𝒢 induced by the condensing function f^c that associates each node of 𝒢 to the strongly connected component it belongs to.


Now, we introduce a novel condensation of a graph 𝒢, denoted as the signed condensation 𝒢^s of 𝒢:

The signed condensation 𝒢^s of a graph 𝒢 is the condensation of 𝒢 induced by the condensing function f^s that associates each node of 𝒢 to the strongly connected component of 𝒢 it belongs to.


Notice that if 𝒢 is unsigned, then 𝒢^c= 𝒢^s. The correspondences between the diverse condensations are illustrated in Figure <ref>. Moreover, we observe that the signed condensation 𝒢^s is a directed acyclic graph. From now on, we call directed acyclic condensation every condensation that is a directed acyclic graph (DAG). We can now give the following definition.


Let us consider a directed acyclic condensation 𝒢^d = (𝒱^d, ℰ^d) of a graph 𝒢=(𝒱,ℰ) induced by a condensing function f^d.
Node i∈𝒱^d belongs to level 1 if ∄ j: (j,i) ∈ℰ^d. Furthemore, 
a node i∈𝒱^d belongs to the l(>1)-th level of 𝒱^d if

    ∀ (j,i)∈ℰ^d ; j∈level p<l.

Moreover, the total number of levels is denoted by ℓ_d and the number of nodes of  𝒢^d in a given level l is n_l^d.  

Given a directed acyclic condensation 𝒢^d of 𝒢, we  associate to each node in 𝒱^d a pair of indexes (a,b): the first will indicate the level the node belongs to and the second its (random) ranking in that level, see Figure <ref>. Accordingly, we can define a function g^d that associates to each (a,b) the corresponding node of 𝒱^d. Now, we can partition (and sort) the set of nodes of 𝒱 as

    𝒱={𝒱_11^d,…,𝒱_1n_1^d^d,…,𝒱_ℓ_d n_ℓ^d^d},

where

    𝒱_ij^d:={t∈𝒱:f^d(t)=g^d(i,j)}.

Moreover, we denote 𝒢_ij^d⊆𝒢 the subgraph induced by 𝒱_ij^d. Consequently, we indicate by 𝒢_ij^c a strongly connected component (SCC) of 𝒢, for all i=1,…,ℓ_c, j=1,…,n_i^c, and that 𝒢^c_11,…,𝒢^c_1h, …, 𝒢_1 n_1^c are its n_1^c≥ 1 aperiodic root strongly connected components (RSCCs). Notice that the number of levels of 𝒢^c, 𝒢^c and 𝒢^s is the same, that is, ℓ_c=ℓ̃_c=ℓ_s:=ℓ. Moreover, for all l = 1,…,ℓ, n_l^c ≤ n^s_l ≤ñ_l^c. Moreover, any SCC of 𝒢 can be classified as of 


  * type 1 if it has no negative weights;

  * type 2 if it has at least one negative weight and is structurally balanced;

  * type 3 if it has at least one negative weight and is structurally unbalanced.


For all h=1,…,n_l, l=1,…,ℓ, we associate to the h-th node of the l-th level of 𝒢^c


  * the h-th (h̃-th) and the h^*-th (h̃^*-th) nodes of the l-th level of 𝒢^s (𝒢^c) such that  
𝒱^c_lh=𝒱^s_l  h∪𝒱^s_l  h^*⊂𝒱^c_lh̃∪𝒱^c_lh̃^*,
if 𝒢^c_lh is of type 1 or type 2;

  * the h-th (h̃-th) node of the l-th level of 𝒢^s such that  
𝒱^c_lh=𝒱^s_l  h⊆𝒱^c_lh̃,
if 𝒢^c_lh is of type 3.

Moreover, we associate to the h̃-th node of the l-th level of 𝒢^c the h-th node of the l-th level of 𝒢^c such that

    𝒱_l h̃^c∩𝒱_lh^c∅.


These associations between the nodes of the condensations are clearly illustrated in Figure <ref>.


§ PROBLEM FORMULATION

Let us consider a signed graph 𝒢 with n nodes and associated weighted adjacency matrix A. 
A subset 𝒞⊂𝒱 comprises the m leaders (sometimes also denoted pinners <cit.>, depending on the context), that is, nodes that have no incoming links.
Denoting x_i∈ℝ the state of the i-th node, the dynamics over the signed graph 𝒢 are described by

    x_i(k+1)=x_i(k)+∑_j =1^N  a_ij(x_j(k)-sign(a_ij)x_i(k)),

for all i=1,…,n, or, equivalently, by

    x(k+1)=Ax(k),

where x=[x_1,…,x_n]^T is the vector of the nodes' states. 

In this paper, we focus on the case in which

    |a_ij|={[    1/|𝒩_i| if  j∈𝒩_i,;          0 otherwise, ].

with 𝒩_i={j∈𝒱:(j,i)∈ℰ} being the set of neighbors' of i,
but the results given in the following can be easily extended to alternative rules for computing a_ij that are consistent with Assumption <ref>. 

Notice that x_i(k+1)=x_i(k)=x_i(0) for all i∈𝒞.
From <cit.>, we give the following definition of containment in signed graphs.

A node i∈𝒱-𝒞 is asymptotically signed contained when

    lim sup_k→+∞| x_i(k)|≤max_j∈𝒞|x_j(0)|,



Network (<ref>) is q-partially signed contained if there exist a subset 𝒬⊆𝒱 of cardinality q such that all the nodes in 𝒬 are asymptotically contained. If q=n-m, then network (<ref>) is signed contained.

Let us denote by ℒ the set of nodes directly controlled by the leaders, that is,

    ℒ={ i∈𝒱 | ∃ a_ji>0,j∈𝒞}.

Then, we can define 𝒦(ℒ):={i∈𝒱 | eq. (<ref>) holds}, as the set of asymptotically contained nodes. For a given cardinality, say d, of the set ℒ, the partial containment control problem consists in finding optimal selection ℒ^*(d) that maximizes the number of contained nodes, that is,


    ℒ^*(d)= max_ℒ| 𝒦(ℒ)|
           s.t.  | ℒ| = d.
 





We observe that the numerical solution of this problem for d>1, although conceptually simple, would require to test for a number of alternative selections of the pinned nodes that is in the order of n!. An extensive search of the optimal solution is therefore computationally prohibitive even for relatively small networks. In what follows, we propose a computationally efficient heuristic approach to find a suboptimal solution of problem (<ref>). 



§ CONVERGENCE ANALYSIS


Before giving our main results, we give  some relevant notation. Specifically, for the h-th SCC of the l-th level, we introduce the stack vector x_lh of the states { x_i }_i∈𝒱^c_lh, and the vector

    y_lh(k):=[x_lh(k)^T, -x_lh(k)^T]^T.

If 𝒢^c_lh is of type 2, y_hl can be viewed as the vector containing all the states of the nodes in 𝒱^c_l h̃∪𝒱^c_l h̃^*. From Lemma <ref>, 𝒢_lh is composed by two disconnected SCCs. 
Therefore, we can find a permutation matrix T_lh such that, defining z_lh(k)=T_lh y_lh(k)=[z_l h̃(k)^T z_lh̃^*(k)^T ]^T, we can write 

    z_lh(k+1)= [   Z_lh̃       0;       0 Z_lh̃^* ] z_lh(k),
 
where Z_lh̃ and Z_lh̃^* are the submatrices extracted from A associated to the nodes in 𝒱_lh̃^c and in 𝒱^c_l h̃^*.

In what follows, for any node h of level l in 𝒢^c corresponding to a type 1 SCC of 𝒢,
we indicate with ξ_lh the left eigenvector associated to the unique eigenvalue λ=1 of block A_lh of matrix A in eq. (<ref>), while, given a type 2 SCC 𝒢^c_lh, we denote 
ξ_lh̃ (ξ_l h̃^*) the left eigenvector associated to the unique eigenvalue λ=1 of Z_lh̃ (Z_l h̃^*). 











By exploiting the condensations introduced in Section <ref>, here we explore the network level by level, to finally provide an algorithm that computes the steady-state configuration of any SCC in the graph.
Let us start by characterizing the asymptotic behaviors of the nodes in the RSCCs (i.e. in the level 1 of 𝒢^c). 

For all h=1,…,n_1^c,


  * if 𝒢_1h^c is of type 1, then

    lim_k→+∞x_i(k)= ξ_1 h^T x_1h(0),     ∀ i∈𝒱^c_1h
 

  * if 𝒢_1h^c is of type 2, the SCC polarizes and

    lim_k→+∞x_i(k)   =ξ_1 𝔥̃^Tz_1 𝔥̃(0)         ∀ i∈𝒱^s_1 𝔥
    lim_k→+∞x_i(k)   =-ξ_1 𝔥̃^*^Tz_1 𝔥̃^*(0)     ∀ i∈𝒱^s_1 𝔥̃^*


  * if 𝒢_1h^c is of type 3, then

    lim_k→ +∞x_1h(k)=0.






    Sketch of the proof:
the proof exploits the fact that the dynamics of the nodes in an SCC of the first level are independent of the dynamics of the nodes not belonging to that SCC. Accordingly, the steady-state values of the nodes in type 1 SCCs can be studied using classic results on consensus, while that of the nodes in type 2 or type 3 SCCs can obtained leveraging results on balanced and unbalanced signed graphs, respectively.        



Next, we define the upstream and the downstream of a node of a DAG.




For each node i of a directed acyclic graph, its upstream (downstream) is the set of nodes, including i itself, from which i is reachable (which i can reach) through a directed path. Moreover, we denote with Υ_lh^𝒢^d the upstream of the node lh of 𝒢^d.

For any node lh of 𝒢^c, δ_i(lh) is the number of nodes of the i-th level of 𝒢^c that are in the upstream of lh, for i=1,…,l-1. Furthermore, we define the set 𝒥_i(lh):= {j_1, …, j_δ_i} as the set of nodes of level i that are in the upstream of node l h, i=1,…,l-1. Set 𝒥_i(lh) can be partitioned as follows:

    𝒥_i(lh)={𝒥_i1(lh),𝒥_i2(lh),𝒥_i3(lh)},

where 𝒥_it(lh)={α∈𝒥_it(lh) | 𝒢_iα^c  is type  t }, t=1,2,3.



We now give an algorithmic procedure to compute the steady-state values of the states of the nodes belonging to a generic SCC of 𝒢.




For all l=2,…,ℓ, h=1,…,n_l^c, the steady-state values x̅_lh of the nodes in 𝒢_lh^c can be computed through the following algorithm

    x̅_1p={[ [[     +ξ^T_1𝔭̃z_1𝔭̃(0)1_|𝒱_1𝔭̃^s|; -ξ^T_1𝔭̃z_1𝔭̃^*(0)1_|𝒱_1𝔭̃^*^s| ]]                                                if 𝒢_1p^c  is of type 1;                                                ξ_1p^Tx_1p(0)1_|𝒱_1p^c|                                                if 𝒢_1p^c  is of type 2;                                                                      0                                                if 𝒢_1p^c  is of type 3 ]., 
           ∀ p ∈𝒥_1(hl),
       x̅_sp=( I-A_sp)^-1∑_λ=1^s-1∑_i∈𝒥_λ (sp)A_sp,λ ix̅_λ i, 
           ∀ s=2,…,l, p∈𝒥_s(hl).





    Sketch of the proof:
the algorithm initialization is a direct application of Theorem <ref>, while the expression of x̅_sp can be derived by induction.   

If ∪_h=1^n_1^c𝒱_1h=𝒞, then network (<ref>) is signed contained.


the thesis directly follows from Theorems <ref>.

The above corollary means that the network is signed contained if the leaders set 𝒞 is connected to each of the f SCCs of the graph of the followers, that is, the subgraph ℱ induced by the node set 𝒱-𝒞. This implies that, to guarantee signed containment, the number of outgoing edges d from the leaders has to be equal or higher than f. The following corollary gives sufficient conditions guaranteeing asymptotic containment of a given SCC of 𝒢.

For all l=2,…,ℓ, h=1,…,n_c^l, the h-th SCC of the l-th level of 𝒢 is signed contained if ∪_k∈Υ_lh^𝒢^c𝒱_1k⊆𝒞.


The dynamics of the nodes in any SCC of the network are decoupled by those of the nodes that are not in its upstream. Then, the thesis follows from Theorem <ref>.

In other words, this means that if the RSCCs of the upstream of the considered SCC are (a subset of) the network leaders, then the SCC is contained.


§ AN ALGORITHM FOR CONTROL DESIGN

Given a network topology 𝒢, the nodes that will be asymptotically signed contained may be more than those of the SCCs fulfilling the assumption of Corollary <ref>. However, this will depend on the initial conditions of the RSCCs of 𝒢 that are not the network leaders. Therefore, if one aims at finding the optimal solution for problem (<ref>), then the knowledge of the initial conditions of all the followers would be necessary for the leaders. In absence of this information, a suboptimal solution maximizing the number of nodes that are guaranteed to be signed contained can be found. Specifically, rather then solving problem (<ref>), we will focus on finding the optimal solution of the following problem:

    ℒ̂(d)   = max_ℒ| ϕ(ℒ)|
    s.t.   
    | ℒ|    = d,
 
where ϕ(ℒ) is the subset of nodes of 𝒢 belonging to SCCs fulfilling the assumptions of Corollary <ref>. 

Contrary to problem (<ref>), the solution of this problem does not require a full exploration of the feasible solutions, and can be translated into an integer linear program (ILP), by adapting the procedure presented in <cit.>. Indeed, by introducing the condensation ℱ^c of the subgraph ℱ of the followers, the algorithm solving problem (<ref>) consists of the following steps:


  * build a new graph 𝒢={𝒱,ℰ} as follows:


  * add to 𝒱 the set of roots r_i of ℱ^c and all the non-roots γ_i of ℱ^c that are in the downstream of no more than d roots r_i;

  * for all pairs γ_i,r_j∈𝒱, add an edge (γ_i,r_j) to ℰ, with associated binary variable y_ij, if in ℱ^c, γ_i is in the downstream of r_j; 

  * add an additional node, π, representing the leader set 𝒞, and connect it to all the r_j in 𝒱 by adding a set of edges (r_j,π) to ℰ, with associated binary variable y_jπ;


  * associate to all edges of the graph 𝒢̅ the following weights:


  * w_ij = |γ_i|, ∀ i, that is, all edges entering the i-th node γ_i have a weight equal to the number of nodes in the SCC γ_i;

  * w_jπ = |r_j|, ∀ j, that is, all edges entering the j-th root r_j have a weight equal to the number of nodes in the SCC r_j;


  * solve the following ILP:

    ymax∑_i∑_j w_ijy_ij + ∑_j w_jπy_jπ
       s.t.
       ∑_j y_jπ = d
       ∑_i y_ij≤ k^out_j y_jπ      ∀ j
    
    k_i^in   ∑_j y_ij≤∑_j | ∃ y_ijy_jπ     ∀ i
        y_ij, y_jπ∈{ 0,1 }       ∀ i,j


where k_i^in and k_i^out are the in- and out-degree of the i-th node of graph 𝒢, respectively.

Let us briefly illustrate the procedure outlined above. We first create a new graph 𝒢, whose nodes are either RSCC of the subgraph of  the followers, or SCCs in the downstream of such RSCCs. Each node representing a RSCC is connected to the SCCs in its downstream. Notice that we do not include any node representing a SCC that has more than d RSCCs in its upstream, and thus cannot be guaranteed to be contained according to Corollary <ref>. 
Then, we add an extra node π to 𝒢 representing the set of leaders, and we connect it to all nodes r_i representing the RSCCs. Finally, we associate to each edge in 𝒢 a weight equal to the number of nodes in the (R)SCC it points to. The solution of the ILP in (<ref>)-(<ref>) is then equivalent to determine the RSCCs that have to be directly controlled, together with the corresponding SCCs that are guaranteed to be contained. Namely, SCC γ_i is contained for all possible initial conditions if there exists a j such that y_ij = 1, and RSCC r_j will be directly controlled if y_jπ = 1. Accordingly, the objective function to be maximized in (<ref>) represents the total number of nodes that we can guarantee to contain according to Corollary <ref>. The constraint (<ref>) guarantees that the directly controlled nodes are d, while  (<ref>) that all the contained nodes are in the downstream of (some of) the leaders. Finally, eq. (<ref>) imposes that the nodes of an SCC are contained only if a node in each of the RSCCs in their upstream is directly controlled by one of the leaders.

Notice that our algorithm only determines which RSCCs of ℱ have to be connected to the set of leaders. Indeed, the selection of the specific node of each RSCC, and the leader connected to it, is indifferent to the objective function of problem (<ref>). Therefore, this selection will be performed randomly in the numerical example that follows. Clearly, the selection may indeed impact on both the convergence rate and on the width of the convex hull in which the followers are asymptotically contained. However, the investigation of these aspects goes beyond the scope of the present work.



 §.§ Numerical example


We consider a signed graph 𝒢 of N=1500 nodes distributed over 4 levels and 15 SCCs, whose dynamics follow equation (<ref>). We assume that only d=2 control inputs can be deployed by the 3 leaders of the network. 
Following the steps of the algorithm, we first build the graph 𝒢̅, which is depicted in Figure <ref>. Then, we solve the ILP  (<ref>)-(<ref>) and find that the leaders should directly control the RSCCs denoted by r_2 and r_3 in Figure <ref> to maximize |ϕ|, that is, the number of followers that are contained regardless of the initial conditions of the network. 
The optimum value of the objective function of problem (<ref>)
is |ϕ(ℒ̂(2))|=508. To validate our results, we simulated the system with the same leaders' states ([-1, 0.5, 1]^T) and two different sets of initial conditions, randomly selected from a uniform distribution in [-20;20]. In both cases, the nodes in ϕ(ℒ̂(2)) (depicted in blue in Figure <ref>) are asymptotically contained. Then, depending on the specific selection of the initial conditions, further nodes of the network might be asymptotically contained, as in the two simulations |𝒦(ℒ̂(2))| is equal to 516 and 843, respectively, see Figure <ref>.








§ CONCLUSION

In this paper, we tackled the containment control problem in a multi-agent discrete-time system where the interactions can be both cooperative and antagonistic. In particular, we focused on the case in which the containment of the entire network is prohibited by constraints on the number of control inputs the leaders can exert on the follower. The partial containment control problem was then defined as searching for the optimal deployment of the available control inputs so as to maximize the number of contained nodes. A preliminary graphical study, based on two alternative condensations of the original graph, allowed the derivation of the conditions guaranteeing the containment of the atomic element of a directed network, that is, a strongly connected component. Leveraging the convergence analyses, an algorithm for maximizing the number of followers we can guarantee to contain was built. Our solution strategy was translated into an integer linear program, and its effectiveness was demonstrated on a testbed examples. Future work will extend this analysis to alternative scenarios in which, for instance, the leaders may not cooperate and have contrasting goals.






IEEEtran

10

url@samestyle








de74
M. H. DeGroot, “Reaching a consensus,” Journal of the American
  Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.

olmu04
R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents
  with switching topology and time-delays,” IEEE Transactions on
  Automatic Control, vol. 49, no. 9, pp. 1520–1533, 2004.

olfa07
R. Olfati-Saber, J. Fax, and R. M. Murray, “Consensus and cooperation in
  networked multi-agent systems,” Proceedings of the IEEE, vol. 95,
  no. 1, pp. 215–233, 2007.

nich10
W. Ni and D. Cheng, “Leader-following consensus of multi-agent systems under
  fixed and switching topologies,” Systems & Control Letters, vol. 59,
  no. 3-4, pp. 209–217, 2010.

jife08
M. Ji, G. Ferrari-Trecate, M. Egerstedt, and A. Buffa, “Containment control in
  mobile networks,” IEEE Transactions on Automatic Control, vol. 53,
  no. 8, pp. 1972–1975, 2008.

care09
Y. Cao and W. Ren, “Containment control with multiple stationary or dynamic
  leaders under a directed interaction graph,” in Proceedings of the
  48th IEEE Conference on Decision and Control, 2009 held jointly with the 2009
  28th Chinese Control Conference, 2009, pp. 3014–3019.

care12
Y. Cao, W. Ren, and M. Egerstedt, “Distributed containment control with
  multiple stationary or dynamic leaders in fixed and switching directed
  networks,” Automatica, vol. 48, no. 8, pp. 1586–1597, 2012.

dedi17
P. DeLellis, A. DiMeglio, F. Garofalo, and F. L. Iudice, “Steering opinion
  dynamics via containment control,” Computational Social Networks,
  vol. 4, no. 12, pp. 1–18, 2017.

pewa15
Z. Peng, D. Wang, Y. Shi, H. Wang, and W. Wang, “Containment control of
  networked autonomous underwater vehicles with model uncertainty and ocean
  disturbances guided by multiple leaders,” Information Sciences, vol.
  316, pp. 163–179, 2015.

cast11
Y. Cao, D. Stuart, W. Ren, and Z. Meng, “Distributed containment control for
  multiple autonomous vehicles with double-integrator dynamics: algorithms and
  experiments,” IEEE Transactions on Control Systems Technology,
  vol. 19, no. 4, pp. 929–938, 2011.

lixi12
H. Liu, G. Xie, and L. Wang, “Necessary and sufficient conditions for
  containment control of networked multi-agent systems,” Automatica,
  vol. 48, no. 7, pp. 1415–1422, 2012.

al13
C. Altafini, “Consensus problems on networks with antagonistic interactions,”
  IEEE Transactions on Automatic Control, vol. 58, no. 4, pp. 935–946,
  2013.

faal11
G. Facchetti, G. Iacono, and C. Altafini, “Computing global structural balance
  in large-scale signed social networks,” Proceedings of the National
  Academy of Sciences, vol. 108, no. 52, pp. 20 953–20 958, 2011.

wafa94
S. Wasserman and K. Faust, Social network analysis: Methods and
  applications.1em plus 0.5em minus 0.4emCambridge University
  Press, 1994, vol. 8.

ha59
F. Harary, “On the measurement of structural balance,” Behavioral
  Science, vol. 4, no. 4, pp. 316–323, 1959.

huzh13
J. Hu and W. X. Zheng, “Bipartite consensus for multi-agent systems on
  directed signed networks,” in 2013 IEEE 52nd Annual Conference on
  Decision and Control.1em plus 0.5em minus 0.4emIEEE, 2013, pp.
  3451–3456.

lich15
J. Liu, X. Chen, T. Başar, and M. A. Belabbas, “Stability of
  discrete-time Altafini's model: a graphical approach,” in 2015 IEEE
  54th Annual Conference on Decision and Control, 2015, pp. 2835–2840.

shpr15
G. Shi, A. Proutiere, M. Johansson, J. Baras, and H. Karl, “Emergent behaviors
  over signed random dynamical networks: State-flipping model,” IEEE
  Transactions on Control of Network Systems, vol. 2, no. 2, pp. 142–153,
  2015.

xica16
W. Xiauo, M. Cao, and K. H. Johansson, “Structural balance and opinion
  separation in trust–mistrust social networks,” IEEE Transactions on
  Control of Network Systems, vol. 3, no. 1, pp. 46–56, 2016.

medu16
D. Meng, M. Du, and Y. Jia, “Interval bipartite consensus of networked agents
  associated with signed digraphs,” IEEE Transactions on Automatic
  Control, vol. 61, no. 12, pp. 3755–3770, 2016.

me17
D. Meng, “Bipartite containment tracking of signed networks,”
  Automatica, vol. 79, pp. 282–289, 2017.

zuso18
S. Zuo, Y. Song, F. L. Lewis, and A. Davoudi, “Bipartite output containment of
  general linear heterogeneous multi-agent systems on signed digraphs,”
  IET Control Theory & Applications, vol. 12, no. 9, pp. 1180–1188,
  2018.

za82
T. Zaslasvsky, “Signed graphs,” Discrete Applied Mathematics, vol. 4,
  no. 1, pp. 47–74, 1982.

he14
J. M. Hendrickx, “A lifting approach to models of opinion dynamics with
  antagonisms,” in 2014 IEEE 53rd Annual Conference on Decision and
  Control, 2014, pp. 2118–2123.

liwa04
X. Li, X. Wang, and G. Chen, “Pinning a complex dynamical network to its
  equilibrium,” IEEE Transactions on Circuits and Systems I: Regular
  Papers, vol. 51, no. 10, pp. 2074–2087, 2004.

podi08
M. Porfiri and M. di Bernardo, “Criteria for global pinning-controllability
  of complex networks,” Automatica, vol. 44, no. 12, pp. 3100–3106,
  2008.

tude14
L. F. R. Turci, P. De Lellis, E. E. N. Macau, M. Di Bernardo, and M. M.
  Simoes, “Adaptive pinning control: A review of the fully decentralized
  strategy and its extensions,” European Physical Journal: Special
  Topics, vol. 223, no. 13, pp. 2649–2664, 2014.

liba16
Y.-Y. Liu and A.-L. Barabási, “Control principles of complex systems,”
  Reviews of Modern Physics, vol. 88, no. 3, p. 035006, 2016.

dega18
P. DeLellis, F. Garofalo, and F. Lo Iudice, “The partial pinning control
  strategy for large complex networks,” Automatica, vol. 89, pp.
  111–116, 2018.







