Modulus Consensus over Networks with Antagonistic Interactions and Switching Topologies\thanksref{footnoteinfo
In this paper, we study the discrete-time consensus problem over networks with antagonistic and cooperative interactions. Following the work by Altafini [IEEE Trans. Automatic Control, 58 (2013), pp. 935--946], by an antagonistic interaction between a pair of nodes updating their scalar states we mean one node receives the opposite of the state of the other and naturally by an cooperative interaction we mean the former receives the true state of the latter. Here the pairwise communication can be either unidirectional or bidirectional and the overall network topology graph may change with time. The concept of modulus consensus is introduced to characterize the scenario that the moduli of the node states reach a consensus. It is proved that modulus consensus is achieved if the switching interaction graph is uniformly jointly strongly connected for unidirectional communications, or infinitely jointly connected for bidirectional communications. We construct a counterexample to underscore the rather surprising fact that quasi-strong connectivity of the interaction graph, i.e., the graph contains a directed spanning tree, is not sufficient to guarantee modulus consensus even under fixed topologies. Finally, simulation results using a discrete-time Kuramoto model are given to illustrate the convergence results showing that the proposed framework is applicable to a class of networks with general nonlinear node dynamics.
discrete.tex
\documentclass[twocolumn]{autart}   % Enable this line and disable the
                                     % preceding line to obtain a two-column
                                     % document whose style resembles the
                                     % printed Automatica style.


\usepackage{graphicx}          % Include this line if your
                               % document contains figures,
\usepackage{amsfonts}
\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{amsmath,color}
\usepackage[longnamesfirst,round]{natbib}
\usepackage[all]{xy}
\usepackage{float}
\usepackage{mathrsfs}
\usepackage{amssymb}
\usepackage{CJK}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                Macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{assumption}{Assumption}[section]

\def\proof{\noindent{\it Proof: }}
\def\QED{\mbox{\rule[0pt]{1.5ex}{1.5ex}}}
\def\endproof{\hspace*{\fill}~\QED\par\endtrivlist\unskip}

\def\d{ {\rm d  }}
\def\sgn{{\rm sgn}}
\def\sig{{\rm sig}}
\def\diag{{\rm diag}}
\def\Co{{\rm Co}}
\def\th{\mbox{\small th}}
\def\T{^{\rm\tiny T}}
\allowdisplaybreaks
\bibliographystyle{elsarticle-harv}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                End Macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\begin{frontmatter}
\title{Modulus Consensus over Networks with Antagonistic Interactions and Switching Topologies\thanksref{footnoteinfo}}

\thanks[footnoteinfo]{This paper was not presented at any IFAC
meeting. Corresponding author Z. Meng. Tel. +46-722-839377.}


\author[KTH]{Ziyang Meng}\ead{ziyangm@kth.se},
\author[KTH]{Guodong Shi}\ead{guodongs@kth.se},
\author[KTH]{Karl H. Johansson}\ead{kallej@kth.se},
\author[RUG]{Ming Cao}\ead{m.cao@rug.nl},
\author[CAS]{Yiguang Hong}\ead{yghong@iss.ac.cn}

\address[KTH]{ACCESS Linnaeus Centre, School of Electrical Engineering,
Royal Institute of Technology, Stockholm 10044, Sweden.}
\address[RUG]{Institute of Technology, Engineering and Management, University of Groningen, the Netherlands.}
\address[CAS]{ Key Laboratory of Systems and Control, Institute of Systems Science, Chinese Academy of Sciences, Beijing 100190, China.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{keyword}
Modulus Consensus; Antagonistic Interactions; Switching Topologies
\end{keyword}

\begin{abstract}
In this paper, we study the discrete-time consensus problem over networks with antagonistic and cooperative interactions. Following the work by Altafini [IEEE Trans. Automatic Control, 58 (2013), pp. 935--946], by an antagonistic interaction between a pair of nodes updating their scalar states we mean one node receives the opposite of the state of the other and naturally by an cooperative interaction we mean the former receives the true state of the latter. Here the pairwise communication can be either unidirectional or bidirectional and the overall network topology graph may change with time. The concept of modulus consensus is introduced to characterize the scenario that
the moduli of the node states reach a consensus. It is proved that modulus consensus is achieved if the switching interaction graph is uniformly jointly strongly connected for unidirectional communications, or infinitely jointly connected for bidirectional communications. We construct a counterexample to underscore the rather surprising fact that quasi-strong connectivity of the interaction graph, i.e., the graph contains a directed spanning tree, is not sufficient to guarantee modulus consensus even under fixed topologies. Finally, simulation results using a discrete-time Kuramoto model are given to illustrate the convergence results showing that the proposed framework is applicable to a class of networks with general nonlinear node dynamics.
\end{abstract}

\end{frontmatter}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Consensus seeking over multi-agent networks has been extensively studied during the past decade, due to its wide applications in various areas including spacecraft formation flying, control of multiple unmanned aerial vehicles, distributed estimation of sensor networks, and collective behaviors of biological swarming (\cite{VicsekEtAl95,LinBrouckeFrancis04}, \\ 
\cite{TannerJadbabaiePappas07}, \\ \cite{CaoMing_TAC08}).  Tremendous successes have been witnessed and various fundamental results have been obtained (\cite{JadbabaieLinMorse03}, \cite{SaberFaxMurray07_IEEE}, \cite{Moreau_TAC05}). In fact, the idea of distributed consensus algorithms was introduced as early as the 1980s for the study of distributed optimization methods in (\cite{Tsitsiklis_TAC86}).

A central problem in consensus study is to investigate the influence of the interaction graph on the convergence or convergence speed of the consensus dynamics. Due to the complex interaction patterns, this interaction graph, which describes the information flow among the nodes, is often time-varying. Both continuous-time and discrete-time models were studied for consensus algorithms with switching interaction graphs and many in-depth understanding was obtained for linear models (\cite{JadbabaieLinMorse03,SaberMurray04,Blondel_CDC2005,Moreau_CDC04,RenBeard05_TAC}, \\
\cite{CaoMing_SIAM08J2}, \cite{HendrickxTAC13}). Nonlinear multi-agent dynamics have also drawn much attention (\cite{LinZhiyun_SIAM07, ShiGuodong_Automatica2009, MengZiyang_Automatica2013}) since in many practical problems the node dynamics are naturally nonlinear, {\em e.g.}, the Kuramoto model (\cite{kuramoto1,kuramoto2}). Recently, consensus algorithms over cooperative-antagonistic networks were also studied in which a node sends the opposite of its true state to its antagonistic neighbors (\cite{AltafiniPlosOne,Altafini_TAC13}).

In this paper, we study consensus protocols over networks with antagonistic interactions under discrete-time dynamics and switching interaction graphs. We introduce the concept of modulus consensus in the sense that the moduli of the node states reach a consensus.  Both unidirectional and bidirectional communications are considered. We show that modulus consensus is achieved if the switching interaction graph is uniformly jointly strongly connected for unidirectional communications, or infinitely jointly connected for bidirectional communications. In addition, a counterexample is constructed which indicates that quasi-strong connectivity of the interaction graph, i.e., the graph has a directed spanning tree, is not sufficient to guarantee modulus consensus even under fixed topology. These results generalize the work in (\cite{AltafiniPlosOne,Altafini_TAC13}), based on a key insight we obtained revealing that any interaction link, being cooperative or antagonistic, always contributes to the agreement of the moduli of the node states.

The remainder of the paper is organized as follows. In
Section \ref{sec:ps}, we give the detailed problem formulation and present the  main results. The  proofs of the results are then given in Section \ref{sec:proofs}.  A simulation example and some brief concluding remarks are given in Sections \ref{sec:simulation}
and \ref{sec:conclusion}.


\section{Problem Formulation and Main Results} \label{sec:ps}
Consider a multi-agent network with agent set $\mathcal{V}=\{1,\dots,n\}$. In the rest of the paper we use  {\it agent} and {\it node} interchangeably. The state-space for the agents is $\mathbb{R}$, and let $x_i\in\mathbb{R}$ denote the state of node $i$. Denote $x=(x_1, x_2,\dots, x_n)\T$.

\subsection{Interaction Graph}
The interaction graph of the network is defined as a sequence of unidirectional graphs, $\mathcal{G}_{k}=(\mathcal{V}, \mathcal{E}_{k})$, $k=0,1,\dots$, on node set $\mathcal{V}$, where $\mathcal{E}_k \subseteq \mathcal{V}\times \mathcal{V}$ is the set of arcs at time $k$. An arc from node $i$ to $j$ is denoted as $(i,j)$. The set of neighbors of node $i$ in $\mathcal{G}_{k}$ is denoted as $\mathcal{N}_i(k):=\{j:(j,i)\in \mathcal{E}_k\}\cup \{i\}$.
The joint graph of $\mathcal{G}$ during time interval $[k_1,k_2)$ is defined by $\mathcal{G}([k_1,k_2))=\bigcup_{k\in[k_1,k_2)}\mathcal{G}(k)=(\mathcal{V},
\bigcup_{k\in[k_1,k_2)}\mathcal{E}_{k})$.

We say node $j$ is reachable from node $i$ in a digraph if there exists a path from $i$ to $j$. A unidirectional graph is quasi-strongly connected if it has a directed spanning tree, {\em i.e.}, there exists at least one node that is reachable to all other nodes. A unidirectional graph is called strongly connected if every two distinct nodes are mutually reachable.
A digraph $\mathcal{G}$ is called bidirectional if for any two nodes $i$ and $j$, $(j,i)\in\mathcal{E}$ if and only if $(i,j)\in\mathcal{E}$. A bidirectional graph is connected if it is connected as an bidirectional graph ignoring the arc directions. We introduce the following definition on the joint connectivity of a sequence of graphs.

\begin{definition} (i). $\{\mathcal{G}_{k}\}_0^\infty$ is uniformly jointly strongly connected if there exists a constant $T\geq 1$ such that $\mathcal{G}([k,k+T))$ is strongly connected for any $k\geq 0$.

(ii). $\{\mathcal{G}_{k}\}_0^\infty$ is uniformly jointly quasi-strongly connected if there exists a constant $T\geq 1$ such that $\mathcal{G}([k,k+T))$ has a directed spanning tree for any $k\geq 0$.


(iii). Suppose $\mathcal{G}_{k}$ is bidirectional for all $k\geq0$. Then $\{\mathcal{G}_{k}\}_0^\infty$ is infinitely jointly connected if $\mathcal{G}([k,+\infty))$ is connected for any $k\geq 0$.
\end{definition}

\subsection{Node Dynamics}\label{sec:control}

The update rule for each node is described by:
\begin{align}
x_i(k+1)=&\sum_{j\in \mathcal{N}_i(k)}a_{ij}(x,k)x_j(k),\notag \\& k=0,1,\dots,
\quad i=1,2,\dots,n,\label{eq:origin}
\end{align}
where $x_i(k)\in\mathbb{R}$ represents of state of agent $i$ at time $k$, $x=[x_1,x_2,\dots,x_n]\T$, and $a_{ij}(x,k)$ represent the weight of arc $(j,i)$. Also, \eqref{eq:origin} can be written in the compact form:
\begin{equation}
x(k+1)=A(x,k)x(k),\quad k=0,1,\dots,\label{eq:matrix}
\end{equation}
where $A(x,k)=[a_{ij}(x,k)]\in \mathbb{R}^{n\times n}$ denotes signed weight matrix.
For $a_{ij}(x,k)$, we impose the following standing assumption.
\vspace{2mm}

\noindent {\bf Assumption.}  (i) $\sum_{j\in \mathcal{N}_i(k)}|a_{ij}(x,k)|=1$ for all $i,x,k$; (ii) there exists $\lambda>0$ such that $|a_{ij}(x,k)|\geq \lambda$ for all $i,j,x,k$.

Clearly under our standing assumption, this model describes the corresponding discrete-time cooperative-antagonistic interactions  introduced by \cite{Altafini_TAC13} in the sense that $a_{ij}(x,k)>0$ represents that $i$ is cooperative to $j$, and $a_{ij}(x,k)<0$ represents that $i$ is antagonistic to $j$.

Introduce $\mathcal{J}=\{y\in \mathbb{R}^{n}:|y_1|=|y_2|=\dots=|y_n|\}$ and define $\|x\|_{\mathcal{J}}=\inf_{y\in \mathcal{J}}\|x-y\|$. \emph{The asymptotic modulus consensus} of system \eqref{eq:origin} is defined as follows.
\begin{defn}\label{def:sign consensus}
System \eqref{eq:origin} achieves asymptotic modulus consensus for any
initial state $x(0)\in \mathbb{R}^{n}$ if
\begin{equation*}
\lim_{k\rightarrow\infty}\|x(k)\|_{\mathcal{J}}=0.
\end{equation*}
\end{defn}
\begin{remark}
We compare the concepts of ``consensus'' (\cite{SaberMurray04}) and ``bipartite consensus'' (\cite{Altafini_TAC13}) with the proposed ``modulus consensus''. Consensus means that states of the agents converge to the same value, {\em i.e.,} $\lim_{k\rightarrow\infty}x_i(k)=\alpha_1$, for all $i=1,2,\dots,n$. Bipartite consensus means that the absolute value of states of the agents converge a non-zero same state, {\em i.e.,} $\lim_{k\rightarrow\infty}|x_i(k)|=\alpha_2>0$, for all $i=1,2,\dots,n$. In contrast, modulus consensus proposed in this paper allows
that different agents converge to zero state, a non-zero same state or split
into two different states. Therefore, the following relationships hold
$$ {\rm consensus} \Rightarrow {\rm bipartite~ consensus} \Rightarrow{\rm modulus~ consensus},$$
and
$$ {\rm modulus ~ consensus} \nRightarrow {\rm bipartite~ consensus}  \nRightarrow {\rm consensus}.$$
\end{remark}



\subsection{Main Results}

The main result for general unidirectional graphs is presented as follows indicating that uniform joint strong connectivity is sufficient for modulus consensus.
\begin{theorem}\label{thm1}
System \eqref{eq:origin} achieves asymptotic modulus consensus for all initial state $x(0)\in \mathbb{R}^{n}$ if $\{\mathcal{G}_{k}\}_0^\infty$ is uniformly jointly strongly connected.
\end{theorem}

\begin{remark}
It is common that consensus may not be achieved
for cooperative-antagonistic multi-agent systems (\cite{Altafini_TAC13}). Instead, the author of (\cite{Altafini_TAC13}) shows that bipartite consensus can be achieved if the sign-symmetric signed graph is strongly connected and structurally balanced.
Compared to the results given in (\cite{Altafini_TAC13}), Theorem \ref{thm1} requires no conditions on the
structural balance structure of the sign graph $\mathcal{G}$. In other words, Theorem \ref{thm1} clearly shows that every
arc, with positive or negative weight, always contributes to the convergence of the moduli of the nodes' states.
\end{remark}

For cooperative networks, it is well-known that asymptotic consensus can be achieved if the interaction graph is uniformly quasi-strongly connected, {\em e.g.,} (\cite{RenBeard05_TAC,CaoMing_SIAM08J1}). Note that quasi-strongly connected condition is weaker  than strongly connected condition. Then a natural question is whether asymptotic modulus consensus can be achieved when the interaction graph is uniformly quasi-strongly connected. We construct the following counterexample showing that quasi-strong connectivity is not sufficient for modulus consensus even with fixed interaction graph.

\vspace{2mm}

\noindent {\bf Counterexample.} Let $\mathcal{V}=\{1,2,3\}$. The initial states are $x_1(0)=1$, $x_2(0)=0$, and $x_3(0)=-1$. The interaction graph is fixed shown in Fig. 1 and the signed weight matrix $A$ (defined after \eqref{eq:matrix}) is given by
\begin{align}
A=[a_{ij}]=\left[\begin{matrix} 1&0&0\\1/3 &1/3& 1/3\\-1/2 &0 &1/2
\end{matrix}\right].
 \end{align}
It is straightforward to check that the interaction graph is quasi-strongly connected. However, the states of the agents remain $x_1(k)=1$, $x_2(k)=0$, and $x_3(k)=-1$, for all $k=1,2,\dots$ under Algorithm \eqref{eq:origin}. Thus, modulus consensus cannot be achieved.

\begin{figure}[hhhhhd]\centering
\begin{tabular} {c}
 \xymatrix{
1 \ar@{->}[rd]_-{+} &  3\ar@{->}[d]_-{+}\ar@{->}[l]_-{-}\\
&  2
} \end{tabular}\caption{Communication topology: ``+'' represents cooperative interaction and ``--'' represents antagonistic interaction} \label{fig1}
\end{figure}

For bidirectional interaction graphs, we present the following result indicating that modulus consensus can be achieved under weaker connectivity conditions than those in Theorem \ref{thm1}.

\begin{theorem}\label{thm2} Suppose $\mathcal{G}_{k}$ is bidirectional for all $k\geq0$.
System \eqref{eq:origin} achieves asymptotic modulus consensus for all initial state $x(0)\in \mathbb{R}^{n}$ if $\{\mathcal{G}_{k}\}_0^\infty$ is infinitely jointly connected.
\end{theorem}


\section{Proofs }\label{sec:proofs}
In this section, we present the proofs of the statements. First a key technical lemma is established, and then the proofs of Theorems \ref{thm1} and \ref{thm2} are presented, respectively.
\subsection{Non-expansiveness of Maximal Modulus}\label{sec:invariant}

We define
$
M(k)=\max_{i\in \mathcal{V}}|x_{i}(k)|.
$
The following lemma establishes that $M(k)$ is non-increasing irrespective of the interaction graph.
\begin{lem}\label{lem:invariant}
For system \eqref{eq:origin}, it holds $M(k+1)\leq M(k)$, for all $k=0,1,\dots$.
\end{lem}
\proof
It follows from the standing assumption that
\begin{align*}
|x_{i}(k+1)|\leq &~\sum_{j\in \mathcal{N}_i(k)}|a_{ij}(x,k)||x_j(k)|
\\ \leq & ~\left(\sum_{j\in \mathcal{N}_i(k)} |a_{ij}(x,k)|\right)\max_{i\in \mathcal{V}}|x_i(k)|
\\=&~ M(k),
\end{align*}
for all $i$, which leads to the conclusion directly.
\endproof

Since a bounded monotone sequence always admits a limit,
Lemma \ref{lem:invariant} implies that for any initial value $x(0)$, there exists a constant $M^*$, such that
$\lim_{k\rightarrow \infty}M(k)=M^*$. We further define
$$
\hbar_{i}=\lim_{k\rightarrow \infty}\sup |x_{i}(k)|, \quad \ell_{i}=\lim_{k\rightarrow \infty}\inf |x_{i}(k)|.
$$
Clearly, it must hold that $0\leq \ell_{i}\leq \hbar_{i}\leq M^*$.
Based on Definition \ref{def:sign consensus}, modulus consensus is achieved if and only if $\hbar_{i}=\ell_{i}=M^*$, $i\in \mathcal{V}$. This serves as our key idea for proving Theorems \ref{thm1} and \ref{thm2}.

We prove the two theorems by contradiction. Based on the fact that $\lim_{k\rightarrow \infty}M(k)= M^*$, it follows that for any $\varepsilon>0$, there exists a $\widehat{k}(\varepsilon)>k_0$ such that
\begin{align*}
|x_{i}(k)|\leq M^*+\varepsilon,~~\forall i\in \mathcal{V}, ~~\forall k\geq \widehat{k}(\varepsilon).
\end{align*}
Now suppose that there exists a node $ {i_1}\in \mathcal{V}$ such that $0\leq \ell_{i_1}< \hbar_{i_1}\leq M^*$. With the definitions of $\ell_{i_1}$ and $\hbar_{i_1}$, for any $\varepsilon>0$, there exist a constant $\ell_{i_1}<\alpha_{1}<\hbar_{i_1}$
%and a subsequence $|x_i(k_0^*)|$, $|x_i(k_1^*)|$, $\dots$, $|x_i(k_l^*)|$, $\dots$, where $0\leq k_0^*<k_1^*<\dots<k_l^*<\dots$ is an increasing sequence of indices such that $|x_i(k_l^*)|\leq\alpha_{1}$, for all $l=0,1,\dots$. Therefore, it follows that there exists
and a time instance $k_1\geq \widehat{k}(\varepsilon)$ such that $|x_{i_1}(k_1)|\leq\alpha_{1}$. This shows that
\begin{align}
|x_{i_1}(k_1)|\leq\hbar_{i_1}-(\hbar_{i_1}-\alpha_{1}) \leq M^*-\xi_1,\label{eq:i1}
\end{align}
where $\xi_1=\hbar_{i_1}-\alpha_{1}>0$. The second inequality is based on the definition of $\hbar_{i_1}$.

\subsection{Proof of Theorem \ref{thm1}}\label{sec:directed}

First of all, it follows from Lemma \ref{lem:invariant} that $|x_{i_1}(k_1+s)|\leq M(k_1)$, for all $s=1,2,\dots$.
Then it must be true that for all $s=1,2,\dots$,
\begin{align*}
|x_{i_1}(k_1+s)|\leq &~\sum_{j\in \mathcal{N}_{i_1}(k_1+s-1)}\left|a_{i_1j}(x,k_1+s-1)\right| \\&\times\left|x_j(k_1+s-1)\right|
\\=&~\left|a_{i_1i_1}(x,k_1+s-1)\right| \left|x_{i_1}(k_1+s-1)\right|
\\&+\sum_{j\in \mathcal{N}_{i_1}(k_1+s-1)\setminus\{ i_1\} }
\!\!\!\!\!\!|a_{i_1j}(x,k_1+s-1)|
\\&\times |x_j(k_1+s-1)|
\\ \leq&~|a_{i_1i_1}(x,k_1+s-1)||x_{i_1}(k_1+s-1)|
\\&+(1-|a_{i_1i_1}(x,k_1+s-1)|)M(k_1).
\end{align*}
Also note that $M(k_1)\leq M^*+\varepsilon$ based on the definition of $M(k_1)$.
It thus follows from \eqref{eq:i1} and our standing assumption that
\begin{align}
|x_{i_1}(k_1+1)|\leq&~ a_{i_1i_1}(x,k_1)|x_{i_1}(k_1)|
\nonumber\\&+(1-a_{i_1i_1}(x,k_1))M(k_1)\nonumber\\
\leq &~a_{i_1i_1}(x,k_1)(M^*-\xi_1)
\nonumber\\&+(1-a_{i_1i_1}(x,k_1))(M^*+\varepsilon)\nonumber\\
\leq &~M^*+\varepsilon-\lambda\xi_1.
\end{align}
By an recursive analysis we can further deduce that  that
\begin{align}\label{r1}
|x_{i_1}(k_1+s)|\leq M^*+\varepsilon-\lambda^s\xi_1, \quad s=1,2,\dots.
\end{align}

Next, we consider the time interval $[k_1,k_1+T)$.
Since $\mathcal{G}([k_1,k_1+T))$ is strongly connected, any other node is reachable from $i_1$ during the time interval $[k_1,k_1+T)$. This implies that
there exists a time $k_2\in [k_1,k_1+T)$ such that $i_1$ is a neighbor of another node $i_2$ at $k_2$. It then follows that
\begin{align*}
|x_{i_2}(k_2+s)|\leq &~\sum_{j\in \mathcal{N}_{i_2}(k_2+s-1)}|a_{i_2j}(x,k_2+s-1)| \\&\times|x_j(k_2+s-1)|
\\=&~|a_{i_2i_1}(x,k_2+s-1)||x_{i_1}(k_2+s-1)|
\\&+\sum_{j\in \mathcal{N}_{i_2}(k_2+s-1)\setminus\{i_1\}}\!\!\!\!\!\!|a_{i_2j}(x,k_2+s-1)| \\&\times|x_j(k_2+s-1)|
\\ \leq&~|a_{i_2i_1}(x,k_2+s-1)| |x_{i_1}(k_2+s-1)|
\\&+(1-|a_{i_2i_1}(x,k_2+s-1)|)M(k_2),
\end{align*}
where we have used the fact that $x_i(k_2+s)\leq M(k_2)$, for all $s=1,2,\dots$, and for all $i\in \mathcal{V}$.
Noting that $M(k_2)\leq M^*+\varepsilon$, it thus follows that
\begin{align*}
|x_{i_2}(k_2+s)| \leq&~|a_{i_2i_1}(x,k_2+s-1)| \\&\times(M^*+\varepsilon-\lambda^{s-1+k_2-k_1}\xi_1)
\\&+(1-|a_{i_2i_1}(x,k_2+s-1)|)(M^*+\varepsilon)\nonumber
\\ \leq &~ M^*+\varepsilon-\lambda^{s+k_2-k_1}\xi_1, \ \ s=1,2,\dots.
\end{align*}
We can further use the fact $k_2-k_1< T$ to obtain
\begin{align}\label{r2}
|x_{i_2}(k_1+s)| \leq M^*+\varepsilon-\lambda^{s}\xi_1, \ \ s=T, T+1,\dots.
\end{align}

We now proceed the argument to time interval $[k_1+T,k_1+2T)$. Again, any other node is reachable from $i_1$ during the time interval $[k_1+T,k_1+2T)$. There exists a time $k_3\in [k_1+T+1,k_1+2T)$ such that either $i_1$ or $i_2$ is a neighbor of $i_3$ ($i_3$ is another node different from $i_1$ and $i_2$) at $k_3$. For any of the two cases we can deduce from (\ref{r1}) and (\ref{r2}) that
\begin{align*}
|x_{i_3}(k_1+s)| \leq ~ M^*+\varepsilon-\lambda^{s}\xi_1,\ \ s=2T,2T+1,\dots.
\end{align*}

The above analysis can be carried out to intervals $[k_1+2T,k_1+3T),\dots,[k_1+(n-2)T,k_1+(n-1)T)$, $i_3,\dots,i_{n-1}$ can be found recursively until they range throughout the whole network. We can therefore finally arrive at
\begin{align*}
M\big(k_1+(n-1)T\big ) \leq &~ M^*+\varepsilon-\lambda^{(n-1)T}\xi_1
\\<&~M^*-{\lambda^{(n-1)T}\xi_1}/{2},
\end{align*}
for sufficient small $\varepsilon$ satifying $\varepsilon<{\lambda^{(n-1)T}\xi_1}/{2}$. Then, it follows from Lemma \ref{lem:invariant} that
\begin{align*}
M(k) <M^*-{\lambda^{(n-1)T}\xi_1}/{2},
\end{align*}
for all $k\geq k_1+(n-1)T$, which contradicts the fact that $\lim_{k\rightarrow \infty}M(k)=M^*$. Therefore the desired theorem holds.
\endproof

\subsection{Proof of Theorem \ref{thm2}}\label{sec:undirected}

In this case, since $\mathcal{G}$ is infinitely jointly connected, the union graph $\mathcal{G}([k_1,\infty])$ is connected. We can therefore well define
$$
k_2:=\inf_k\big\{k\geq k_1, \mathcal{N}_{i_1}(k)\neq \emptyset\big\}.
$$
We also denote $\mathcal{V}_1=\mathcal{N}_{i_1}(k_2)$. Obviously, we have that $|x_{i_1}(k_2)|=|x_{i_1}(k_1)|\leq M^*-\xi_1$.
Therefore, following the similar analysis by which we obtain (\ref{r1}) and (\ref{r2}), we know that
%$$
%|x_{i_1}(k_2+1)|\leq M^*+\varepsilon-\lambda\xi_1,
%$$ and
$$
|x_{i}(k_2+1)|\leq M^*+\varepsilon-\lambda\xi_1,\ i\in\mathcal{V}_1.
$$

Similarly, since the union graph $\mathcal{G}([k_2+1,\infty])$ is connected, we can continue to define
$$
k_3:=\inf_k\Big\{k\geq k_2+1, \bigcup_{i\in \mathcal{V}_1}\mathcal{N}_{i}(k)\neq \emptyset\Big\}.
$$
We also denote $\mathcal{V}_2=\bigcup_{i\in \mathcal{V}_1}\mathcal{N}_{i}(k_3)$. Note that $\{i_1\}\subseteq \mathcal{V}_1\subseteq \mathcal{V}_2$ by the definition of neighbor sets. Now that $k_3$ is the first time instant that there is another node connected to ${\mathcal{V}_1}$, we can apply Lemma \ref{lem:invariant} to the subset $\mathcal{V}_1$ for time interval $[k_2+1,k_3]$, and deduce that
 $$
 |x_{i}(k_3)|\leq M^*+\varepsilon-\lambda\xi_1,\  i\in{\mathcal{V}_1}.
 $$
It then follows from the same analysis that $$
|x_{i}(k_3+1)|\leq M^*+\varepsilon-\lambda^2\xi_1,\ i\in\mathcal{V}_2.
$$

The above argument can be carried recursively for  $\mathcal{V}_3$, $\mathcal{V}_4$, $\dots$ until $\mathcal{V}_m =\mathcal{V}$ for some $m\leq n-1$.  The corresponding $k_m$ can be found  such that $$
|x_{i}(k_m+1)|\leq M^*+\varepsilon-\lambda^{m}\xi_1,\ \ i\in \mathcal{V}.
$$
 This indicates that
\begin{align*}
M(k_m+1) \leq ~ M^*+\varepsilon-\lambda^{m}\xi_1<M^*-\lambda^{m}\xi_1/2,
\end{align*}
for sufficient small $\varepsilon$ satisfying $\varepsilon<\lambda^{n-1}\xi_1/2$. Again this contradicts the fact that $\lim_{k\rightarrow \infty}M(k)=M^*$. We have completed the proof and the desired theorem holds.
\endproof



\section{Numerical Example}\label{sec:simulation}

Consider the following discrete-time Kuramoto oscillator systems with antagonistic and cooperative links:
\begin{equation}
\theta_i(k+1)=\theta_i(k)-\mu\sum_{j\in \mathcal{N}_i(k)\setminus \{i\}}\sin\Big(\theta_i(k)-R_{ij}(k)\theta_j(k)\Big),\label{eq:oscillator}
\end{equation}
where $\theta_i(k)$ denotes the state of node $i$ at time $k$, $\mu>0$ is the stepsize, and $R_{ij}(k)\in\{1,-1\}$ represents the cooperative or antagonistic
relationship between node $i$ and node $j$. Note that with $R_{ij}(k)\equiv 1$, system \eqref{eq:oscillator} corresponds to the classical Kuramoto oscillator model (\cite{kuramoto1,kuramoto2}). Let $\delta\in (0,\frac{\pi}{2})$ be a given constant and suppose $\theta_i(0)\in(-\frac{\pi}{2}+\delta,\frac{\pi}{2}-\delta)$ for all $i\in\mathcal{V}$. Here $\delta$ can be any positive constant sufficiently small.

Algorithm \eqref{eq:oscillator} can be rewritten as
\begin{align*}
\theta_i(k+1)=&~\theta_i(k)-\mu\!\!\!\sum_{j\in \mathcal{N}_i(k)\setminus \{i\}}\!\!\!\frac{\sin(\theta_i(k)-R_{ij}(k)\theta_j(k))}{\theta_i(k)-R_{ij}(k)\theta_j(k)}
\\&~\times(\theta_i(k)-R_{ij}(k)\theta_j(k)).
\end{align*}
Note that the function $\frac{\sin x}{x}$ is well-defined for $x\in(-\infty,\infty)$.
Therefore, defining
$$
a_{ij}(\theta,k)=\frac{\sin(\theta_i(k)-R_{ij}(k)\theta_j(k))}{\theta_i(k)-R_{ij}(k)\theta_j(k)}R_{ij}(k), \ \ j\in \mathcal{N}_i(k)\setminus \{i\}.
$$
and $a_{ii}(\theta,k)=1-\mu\sum_{j\in \mathcal{N}_i(k)\setminus \{i\}}|a_{ij}(\theta,k)|$, where $\theta=[\theta_1,\theta_2,\dots,\theta_n]\T$, Algorithm \eqref{eq:oscillator} is re-written into the form of \eqref{eq:origin}.

Moreover, Lemma \ref{lem:invariant} ensures that
\begin{equation*}
0<\lambda^*\leq \frac{\sin(\theta_i(k)-R_{ij}(k)\theta_j(k))}{\theta_i(k)-R_{ij}(k)\theta_j(k)}\leq 1,
\end{equation*}
where $\lambda^*=\frac{\sin(\pi-2\delta)}{\pi-2\delta}$. This gives us $|a_{ij}(\theta,k)|\geq \lambda^*$, for all $i$ and $j\in \mathcal{N}_i(k)\setminus \{i\}$. In addition,
by selecting $\mu<\frac{1-\lambda^*}{n}$, we can also guarantee that $|a_{ii}(\theta,k)|\geq \lambda^*$ for all $k$.

Therefore, given $\mu<\frac{1-\lambda^*}{n}$, modulus consensus, {\em i.e.,} $\lim_{k\rightarrow\infty}(|\theta_i(k)|-|\theta_j(k)|)=0$, $i,j\in \mathcal{V}$, is achieved under \eqref{eq:oscillator}, if $\{\mathcal{G}_k\}_0^\infty$ is uniformly jointly strongly connected for unidirectional graphs, or infinitely jointly connected for bidirectional graphs according to Theorems \ref{thm1} and \ref{thm2}.

We next verify the above arguments using simulations. For the case of unidirectional communication topology, we assume that
the communication topology switches periodically as Fig. \ref{fig2}
when the systems are at time instants $\eta_l=l~s$, $l=1,2,\dots$, where
$\mathcal{G}_1$, $\mathcal{G}_2$, $\mathcal{G}_3$ are represented in Figs. \ref{fig-comm-di1}, \ref{fig-comm-di2}, and \ref{fig-comm-di3}.
\begin{figure}[hhhhhd]\centering
\begin{tabular} {cc}
 \xymatrix{
\mathcal{G}_1 \ar@{->}[r] &  \mathcal{G}_2\ar@{->}[r] &  \mathcal{G}_3\ar@{->}[r]&  \mathcal{G}_1\ar@{->}[r] &\dots
} \end{tabular}\caption{Switching communication topology} \label{fig2}
\end{figure}
The signed weight matrices associated with $\mathcal{G}_1$, $\mathcal{G}_2$, $\mathcal{G}_3$ are given by
$$
A_1=\left[\begin{matrix} 1&0&0\\0 &1& 0\\-0.5 &0 &0.5
\end{matrix}\right], \quad A_2=\left[\begin{matrix} 1&0&0\\0 &0.5& -0.5\\0 &0 &1
\end{matrix}\right],$$
$$ A_3=\left[\begin{matrix} 0.5&0.5&0\\0 &1& 0\\0 &0.5 &0.5
\end{matrix}\right].
$$
The initial states are $x_1(0)=-1.5$, $x_2(0)=1$, and $x_3(0)=0$ and $\mu$ is chosen as $\mu=0.1$. Fig. 6 shows the convergence of states over unidirectional switching communication topologies. We see that
modulus consensus is achieved for this group of oscillators
with antagonistic interactions and switching topologies, in accordance with the conclusion from Theorem \ref{thm1}. Note that states of all the agents converge to zero, instead of achieving bipartite consensus.

\begin{figure}[htbp]
\begin{minipage}[t]{0.3\linewidth}
~~~~~~~~~~ \xymatrix{
1 &  3\ar@{->}[l]_-{-}\\
&  2
}
\caption{$\mathcal{G}_1$}\label{fig-comm-di1}
\end{minipage}
\begin{minipage}[t]{0.3\linewidth}
\centering
~~ \xymatrix{
1 &  3\\
&  2\ar@{->}[u]_-{-}
}
\caption{$\mathcal{G}_2$} \label{fig-comm-di2}
\end{minipage}
\begin{minipage}[t]{0.3\linewidth}
\centering
~~  \xymatrix{
1\ar@{->}[rd]_-{+}  &  3\ar@{->}[d]_-{+}\\
&  2
}
\caption{$\mathcal{G}_3$} \label{fig-comm-di3}
\end{minipage}
\end{figure}

\begin{figure}\label{fig-directed}
\begin{center}
\includegraphics[width=8.5cm,height=6.8cm]{1.eps}
\caption{Convergence for unidirectional communication topology}
 \end{center}
\end{figure}

For the case of bidirectional communication topology, we assume the communication topology switches between $\mathcal{G}_4$ and $\mathcal{G}_5$ in Figs. \ref{fig-comm-un1} and \ref{fig-comm-un2}. The topology remains $\mathcal{G}_4$ but at time intervals $[l^2,l^2+1]$, where the topology is $\mathcal{G}_5$, $l=1,2,\dots$. The signed weight matrices associated with $\mathcal{G}_4$, $\mathcal{G}_5$ are
$$
A_4=\left[\begin{matrix} 0.5&0&-0.5\\0 &1& 0\\-0.5 &0 &0.5
\end{matrix}\right], \quad A_5=\left[\begin{matrix} 1&0&0\\0 &0.5& 0.5\\0 &0.5 &0.5
\end{matrix}\right].
 $$
The initial states are $x_1(0)=-1.5$, $x_2(0)=1$, and $x_3(0)=0$ and $\mu$ is chosen as $\mu=0.1$. Fig. 9 shows the convergence of states over bidirectional switching communication topologies. We see that
modulus consensus is achieved for this group of oscillators
with antagonistic interactions and switching topologies, in accordance with the conclusion from Theorem \ref{thm2}. Bipartite consensus is achieved in this case.

\begin{figure}[htbp]
\begin{minipage}[t]{0.45\linewidth}
\centering
~~ \xymatrix{
1 &  3\ar@{<->}[l]_-{-}\\
&  2
}
\caption{$\mathcal{G}_4$} \label{fig-comm-un1}
\end{minipage}
\begin{minipage}[t]{0.45\linewidth}
\centering
~ \xymatrix{
1 &  3\\
&  2\ar@{<->}[u]_-{+}
}
\caption{$\mathcal{G}_5$} \label{fig-comm-un2}
\end{minipage}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=8.5cm,height=6.8cm]{2.eps}\label{fig-undirected}
\caption{Convergence for bidirectional  communication topology}
 \end{center}
\end{figure}

\section{Conclusions}\label{sec:conclusion}

In this paper, we studied consensus problem of multi-agent systems over cooperative-antagonistic network in a discrete-time setting. We first defined modulus consensus and both the cases of unidirectional communication topologies and bidirectional communication topologies were considered. The cases of jointly connectivity were studied and it was proven that modulus consensus can be achieved if the communication topology is uniformly jointly strongly connected or is infinitely jointly connected. In addition, we also give an example to show that the communication topology is uniformly quasi-strongly connected is not sufficient to guarantee modulus consensus. Examples are given to explain coordination of multiple nonlinear systems with antagonistic interactions using the proposed algorithms. Future works include considering antagonistic interactions for consensus problems for higher-order dynamics dynamics and investigating time-delay influence.


%%%%%%%%%%%%%% begin Bibliography %%%%%%%%%%%%%%%%%

%\bibliographystyle{IEEEtran}
\bibliography{refs}
%%%%%%%%%%%%%%%% end Bibliography %%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%% biosketches and photos %%%%%%%%%%%%%%%%%


\end{document}

discrete.bbl
\begin{thebibliography}{22}
\expandafter\ifx\csname natexlab\endcsname\relax\def\natexlab#1{#1}\fi
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi

\bibitem[{Altafini(2012)}]{AltafiniPlosOne}
Altafini, C., 2012. Dynamics of opinion forming in structurally balanced social
  networks. PloS One~(7(6):e38135).

\bibitem[{Altafini(2013)}]{Altafini_TAC13}
Altafini, C., 2013. Consensus problems on networks with antagonistic
  interactions. IEEE Transactions Automatic Control 58~(4), 935--946.

\bibitem[{Blondel et~al.(2005)Blondel, Hendrickx, Olshevsky, and
  Tsitsiklis}]{Blondel_CDC2005}
Blondel, V.~D., Hendrickx, J.~M., Olshevsky, A., Tsitsiklis, J.~N., 2005.
  Convergence in multiagent coordination, consensus, and flocking. In: 44th
  IEEE Conference on Decision and Control. pp. 2996--3000.

\bibitem[{Cao et~al.(2008{\natexlab{a}})Cao, Morse, and
  Anderson}]{CaoMing_TAC08}
Cao, M., Morse, A.~S., Anderson, B. D.~O., 2008{\natexlab{a}}. Agreeing
  asynchronously. IEEE Transactions on Automatic Control 53~(8), 1826--1838.

\bibitem[{Cao et~al.(2008{\natexlab{b}})Cao, Morse, and
  Anderson}]{CaoMing_SIAM08J1}
Cao, M., Morse, A.~S., Anderson, B. D.~O., 2008{\natexlab{b}}. Reaching a
  consensus in a dynamically changing environment: A graphical approach. SIAM
  Journal of Control and Optimization 47~(2), 575--600.

\bibitem[{Cao et~al.(2008{\natexlab{c}})Cao, Morse, and
  Anderson}]{CaoMing_SIAM08J2}
Cao, M., Morse, A.~S., Anderson, B. D.~O., 2008{\natexlab{c}}. Reaching a
  consensus in a dynamically changing environment: convergence rates,
  measurement delays, and asynchronous events. SIAM Journal of Control and
  Optimization 47~(2), 601--623.

\bibitem[{Hendrickx and Tsitsiklis(2013)}]{HendrickxTAC13}
Hendrickx, J.~M., Tsitsiklis, J.~N., 2013. Convergence of type-symmetric and
  cut-balanced consensus seeking systems. IEEE Transactions Automatic Control
  58~(1), 214--218.

\bibitem[{Jadbabaie and Barahona(2004)}]{kuramoto2}
Jadbabaie, A., Barahona, M., 2004. On the stability of the {K}uramoto model of
  coupled nonlinear oscillators. In: 43th IEEE Conference on Decision and
  Control. Boston, MA, USA, pp. 4296--4301.

\bibitem[{Jadbabaie et~al.(2003)Jadbabaie, Lin, and
  Morse}]{JadbabaieLinMorse03}
Jadbabaie, A., Lin, J., Morse, A.~S., 2003. Coordination of groups of mobile
  autonomous agents using nearest neighbor rules. {IEEE} Transactions on
  Automatic Control 48~(6), 988--1001.

\bibitem[{Lin et~al.(2004)Lin, Broucke, and Francis}]{LinBrouckeFrancis04}
Lin, Z., Broucke, M., Francis, B., April 2004. Local control strategies for
  groups of mobile autonomous agents. {IEEE} Transactions on Automatic Control
  49~(4), 622--629.

\bibitem[{Lin et~al.(2007)Lin, Francis, and Maggiore}]{LinZhiyun_SIAM07}
Lin, Z., Francis, B., Maggiore, M., 2007. State agreement for continuous-time
  coupled nonlinear systems. SIAM Journal of Control and Optimization 46~(1),
  288--307.

\bibitem[{Meng et~al.(2013)Meng, Lin, and Ren}]{MengZiyang_Automatica2013}
Meng, Z., Lin, Z., Ren, W., 2013. Robust cooperative tracking for multiple
  non-identical second-order nonlinear systems. Automatica 49~(8), 2363--2372.

\bibitem[{Moreau(2004)}]{Moreau_CDC04}
Moreau, L., 2004. Stability of continuous-time distributed consensus
  algorithms. In: 43th IEEE Conference on Decision and Control. Atlantis,
  Bahamas, pp. 3998--4003.

\bibitem[{Moreau(2005)}]{Moreau_TAC05}
Moreau, L., 2005. Stability of multi-agent systems with time-dependent
  communication links. {IEEE} Transactions on Automatic Control 50~(2),
  169--182.

\bibitem[{Olfati-Saber et~al.(2007)Olfati-Saber, Fax, and
  Murray}]{SaberFaxMurray07_IEEE}
Olfati-Saber, R., Fax, J.~A., Murray, R.~M., 2007. Consensus and cooperation in
  networked multi-agent systems. Proceedings of the {IEEE} 95~(1), 215--233.

\bibitem[{Olfati-Saber and Murray(2004)}]{SaberMurray04}
Olfati-Saber, R., Murray, R.~M., 2004. Consensus problems in networks of agents
  with switching topology and time-delays. {IEEE} Transactions on Automatic
  Control 49~(9), 1520--1533.

\bibitem[{Ren and Beard(2005)}]{RenBeard05_TAC}
Ren, W., Beard, R.~W., 2005. Consensus seeking in multiagent systems under
  dynamically changing interaction topologies. {IEEE} Transactions on Automatic
  Control 50~(5), 655--661.

\bibitem[{Shi and Hong(2009)}]{ShiGuodong_Automatica2009}
Shi, G., Hong, Y., 2009. Global target aggregation and state agreement of
  nonlinear multi-agent systems with switching topologies. Automatica 45~(5),
  1165--1175.

\bibitem[{Strogatz(2000)}]{kuramoto1}
Strogatz, S.~H., 2000. From {K}uramoto to {C}rawford: exploring the onset of
  synchronization in populations of coupled oscillators. Physica D: Nonlinear
  Phenomena 143~(1-4), 1--20.

\bibitem[{Tanner et~al.(2007)Tanner, Jadbabaie, and
  Pappas}]{TannerJadbabaiePappas07}
Tanner, H.~G., Jadbabaie, A., Pappas, G.~J., 2007. Flocking in fixed and
  switching networks. {IEEE} Transactions on Automatic Control 52~(5),
  863--868.

\bibitem[{Tsitsiklis et~al.(1986)Tsitsiklis, Bertsekas, and
  Athans}]{Tsitsiklis_TAC86}
Tsitsiklis, J.~N., Bertsekas, D., Athans, M., 1986. Distributed asynchronous
  deterministic and stochastic gradient optimization algorithms. IEEE
  Transactions Automatic Control 31~(9), 803--812.

\bibitem[{Vicsek et~al.(1995)Vicsek, Czirok, Jacob, Cohen, and
  Schochet}]{VicsekEtAl95}
Vicsek, T., Czirok, A., Jacob, E.~B., Cohen, I., Schochet, O., 1995. Novel type
  of phase transitions in a system of self-driven particles. Physical Review
  Letters 75~(6), 1226--1229.

\end{thebibliography}
