# Distributed Design of Controllable and Robust Networks using
Zero Forcing and Graph Grammars

Priyanshkumar I. Patel∗, Johir Suresh∗, and Waseem Abbas ∗Authors contributed
equally to the work.Authors are with the University of Texas at Dallas,
Richardson, TX, USA (Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>waseem.abbas@utdallas.edu).

###### Abstract

This paper studies the problem of designing networks that are strong
structurally controllable, and robust simultaneously. For given network
specifications, including the number of nodes $N$, the number of leaders
$N_{L}$, and diameter $D$, where $2\leq D\leq N/N_{L}$, we propose graph
constructions generating strong structurally controllable networks. We also
compute the number of edges in graphs, which are maximal for improved
robustness measured by the algebraic connectivity and Kirchhoff index. For the
controllability analysis, we utilize the notion of zero forcing sets in
graphs. Additionally, we present graph grammars, which are sets of rules that
agents apply in a distributed manner to construct the graphs mentioned above.
We also numerically evaluate our methods. This work exploits the trade-off
between network controllability and robustness and generates networks
satisfying multiple design criteria.

###### Index Terms:

Strong structural controllability, zero forcing sets, network design, network
robustness.

##  I Introduction

The distributed design of networks satisfying multiple design criteria is
generally a challenging problem. From a network control perspective,
controllability and robustness to failures are two of the vital design
attributes. Network controllability is the ability to manipulate and drive the
network to desired configurations (states) due to external control signals
(inputs), which are injected into the network through a subset of nodes called
_leaders_ (e.g., [pasqualetti2014controllability]). Network robustness has
many interpretations, which can be categorized as functional and structural
robustness [abbas2012]. The former is related to the network’s functioning in
the presence of noise and perturbations and later describes the ability to
preserve the network’s structural attributes despite node/edge failures
[zelazo2015robustness, young2015new]. Interestingly, these two interpretations
are related to each other in the context of network control systems and can be
measured through common graph metrics, such as algebraic connectivity and
Kirchhoff index $K_{f}$ [ellens2011effective, wang2010graphs,
siami2013fundamental].

It is well studied that network controllability and robustness can be
conflicting, i.e., for a given set of network parameters, networks requiring
few leaders for complete controllability might exhibit poor robustness
properties [abbas2020tradeoff, pasqualetti2020fragility]. For instance, for a
given number of nodes $N$, path graphs require a single leader node for
complete controllability; however, they have minimum robustness. Similarly,
fixing $N$ and diameter $D$, networks with maximum robustness (as measured by
the algebraic connectivity and $K_{f}$) are clique chains [wang2010graphs,
ellens2011effective]; however, they require many leaders $(N-D)$ for complete
controllability [abbas2020tradeoff]. So, an important issue is, _how can we
design networks in a distributed manner such that networks can be controlled
with few leaders (inputs) and exhibit high robustness simultaneously?_ This
question becomes more intriguing when the network controllability is
considered in the strong structural sense due to computational complexity
issues (e.g., [chapman2013strong, shabbir2022computation, menara2017number,
jia2019strong]). Network controllability generally depends on the edge
weights; however, edge weights are inconsequential in the case of strong
structural controllability (SSC), which essentially depends on the network
structure and the leader set.

In this paper, we propose distributed designs of networks that are strong
structurally controllable for a given number of nodes $N$ and leaders $N_{L}$.
At the same time, these networks are robust due to maximal edge sets. For
distributed construction of such networks, we utilize graph grammars
[klavins2007programmable, yim2007modular, abbas2011hierarchical]. To ensure
SSC, we use the relationship between the notion of zero forcing in graphs and
SSC [monshizadeh2014zero, mousavi2017structural]. Our proposed designs are
flexible in the sense that for fixed $N$ and $N_{L}$, they can produce graphs
with varying graph parameters such as the diameter $D$ and robustness, as
measured by the Kirchhoff index and algebraic connectivity of graphs while
ensuring that graphs remain strong structurally controllable. Thus, the
network constructions exploit the trade-off between network controllability
and robustness. Our main contributions are summarized below:

  * •

For given $N$ (total number of nodes) and $N_{L}$ (number of leaders), we
construct strong structurally controllable graphs with $N_{L}$ leaders and
maximal edge sets. For SSC, we utilize the idea of zero forcing sets.

  * •

Our designs enable generating graphs with diameter $D$, where $2\leq D\leq
N/N_{L}$, while ensuring that each such graph has a maximal edge set and is
strong structurally controllable with $N_{L}$ leaders. Since network diameter
influences its robustness, we can attain networks with various robustness. We
also numerically evaluate the robustness of such graphs using algebraic
connectivity and Kirchhoff index metrics.

  * •

Furthermore, we provide distributed ways to construct the above graphs using
graph grammars, a set of rules that nodes implement locally to achieve the
desired network structure. Finally, we numerically evaluate the proposed
schemes.

Our problem setting is similar to the one in [abbas2020tradeoff], albeit with
some significant differences. We use a simpler zero forcing method to analyze
strong structural controllability in networks, whereas [abbas2020tradeoff]
utilizes graph distances for this purpose. Additionally, for given $N$ and
$N_{L}$, the graphs generated in [abbas2020tradeoff] are of fixed diameter. We
provide multiple constructions enabling graphs with different diameters and
robustness. Finally, we provide distributed constructions of networks using
graph grammars, which are not in [abbas2020tradeoff].

The rest of the paper is organized as follows: Section II presents preliminary
ideas and sets up the problem. Section III is the main section providing graph
constructions for given specifications along with the controllability and
robustness analysis of the constructions. Section LABEL:subsec:GGs provides
graph grammars to construct the proposed graphs in a distributed manner.
Finally, Section LABEL:sec:conclusion concludes the paper.

##  II Preliminaries

###  II-A Notations

We consider a multi-agent network system as an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$. The _vertex set_ $\mathcal{V}$ =
$\\{v_{1},v_{2},\dots,v_{N}\\}$ represents the agents (nodes), and the edge
set $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ represents the edges
between nodes. We denote the edge between nodes $u$ and $v$ by an unordered
pair $(u,v)$. Node $u$ is a _neighbor_ of node $v$ if $(u,v)\in\mathcal{E}$.
The number of nodes in the neighborhood of $u$ is the _degree_ of $u$. The
_distance_ between nodes $u$ and $v$, denoted by $d(u,v)$, is the number of
edges in the shortest path between $u$ and $v$. The _diameter_ of
$\mathcal{G}$, denoted by $D$, is the maximum distance between any two nodes
in $\mathcal{G}$. A _path_ of length $k$ is a sequence of nodes that form a
subgraph of $\mathcal{G}$, $P_{k}:=<u_{0},u_{1},u_{2},\cdots,u_{k}>$, where
$(u_{i},u_{i+1})\in\mathcal{E},\;\forall i\in\\{0,\cdots,k-1\\}$. The _leader
- follower_ system associated with graph $\mathcal{G}$ is defined by the
following state-space representation:

$\dot{x}(t)=Mx(t)+Bu(t).$ (1)

Here, $x(t)\in\Re^{n}$ is the state of the system and $M\in\mathcal{M(G)}$ is
a system matrix, where $\mathcal{M(G)}$ is a family of symmetric matrices
associated with an undirected graph $\mathcal{G}$ defined below.

$\begin{split}\mathcal{M(G)}=\\{M\in\Re^{n\times n}&|M=M^{T},\text{and
for}\>i\neq j,\\\ &M_{ij}\neq
0\Leftrightarrow(i,j)\in\mathcal{E(G)}\\}.\end{split}$ (2)

Note that $\mathcal{M(G)}$ includes the adjacency and Laplacian matrices of
$\mathcal{G}$. In (1), $u(t)\in\Re^{m}$ is the input signal, and
$B\in\Re^{n\times m}$ is the input matrix containing information about the
leader nodes through which inputs are injected into the network. For a set of
leaders labelled $\\{\ell_{1},\ell_{2},\dots,\ell_{m}\\}\subseteq\mathcal{V}$,
we define the input matrix as follows.

$B_{ij}=\begin{cases}1&\text{if}\>v_{i}=\ell_{j},\\\
0&\text{otherwise.}\end{cases}$ (3)

We are interested in designing networks with the above dynamics that are
strong structurally controllable and maximally robust. Next, we discuss the
controllability and robustness measures we utilize to evaluate our graphs.

###  II-B Network Controllability Measure

For the strong structural controllability analysis, we utilize the notion of
_zero forcing sets_ in graphs. Considering a system defined on graph
$\mathcal{G}$, the pair $(M,B)$ is a _controllable pair_ if there exists an
input $u(t)$ that could drive the system from any initial state $x(t_{0})$ to
any final state $x(t_{f})$ in a given time period $t=t_{f}-t_{0}$.

  * Definition

_(Strong Structural Controllability (SSC))_ A given graph $\mathcal{G}$ with a
set of leader nodes
$\\{\ell_{1},\ell_{2},\dots,\ell_{m}\\}\subseteq\mathcal{V}$, and the
corresponding $B$ matrix is said to be _strong structurally controllable_ if
and only if $(M,B)$ is a controllable pair $\forall\>M\in\mathcal{M}$.

In [monshizadeh2014zero], Monshizadeh et al. provides a graph-theoretic
characterization of SSC in networks in terms of zero forcing in graphs
explained below.

  * Definition

_(Zero Forcing Process)_ Consider a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ whose nodes are initially colored
either black, or white. If a node $v\in\mathcal{V}$ is black and has exactly
one white neighbor $u$, then $v$ forces $u$ to change its color to black. Zero
forcing is a process of applying this color change rule until no black node
exists with only one white neighbor.

For a given set of initial black nodes, there can be multiple ways to execute
the zero forcing process; however, the set of black nodes at the end of the
process will always be the same [work2008zero]. If there is a unique way of
proceeding the zero forcing process in a graph $\mathcal{G}$, we call it a
_unique zero forcing process_. Moreover, the set of black nodes obtained at
the end of the zero forcing process is called the _derived set_.

  * Definition

_(Zero Forcing Set (ZFS))_ Consider a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with an initial set of black nodes
(leaders) $\\{\ell_{1},\ell_{2},\dots,\ell_{m}\\}\subseteq\mathcal{V}$. Let
$\mathcal{V}^{\prime}$ be the derived set at the of the zero forcing process,
then $\\{\ell_{1},\ell_{2},\dots,\ell_{m}\\}$ is a ZFS if and only if
$\mathcal{V}^{\prime}=\mathcal{V}$.

Figure 1 illustrates the idea of a ZFS.

Figure 1: Set of nodes $\\{u_{1},u_{2},u_{3}\\}$ is a ZFS as the corresponding
derived set $\mathcal{V}^{\prime}$ contains all the nodes in the graph.

Monshizadeh et al. [monshizadeh2014zero] characterizes the minimum leader set
for SSC in terms of ZFS of the network graph, showing that the network is
strong structurally controllable if and only if the leader set is a ZFS. In
this work, since we aim to design strong structurally controllable networks
with $N_{L}$ leaders, the leader sets will always be zero forcing sets of the
corresponding graphs.

###  II-C Network Robustness Measures

To analyze the robustness of the proposed graphs, we use widely used metrics,
_algebraic connectivity_ and _Kirchhoff index_. _Algebraic connectivity_ of a
graph $\mathcal{G}$ (also known as the Fiedler value) is the second smallest
eigenvalue of its Laplacian matrix. A higher value of algebraic connectivity
indicates higher robustness.

_Kirchhoff index_ of a graph $\mathcal{G}$, denoted as $K_{f}(\mathcal{G})$,
is

$K_{f}(\mathcal{G})=N\sum_{i=2}^{N}\frac{1}{\lambda_{i}},$ (4)

where $N$ is the total number of nodes in the graph $(\mathcal{G})$ and
$\lambda_{2}\leq\lambda_{3}\leq\cdots\lambda_{N}$ are the eigenvalues of the
Laplacian of the graph $(\mathcal{G})$. Robustness and the value of Kirchhoff
index of a graph are inversely related, i.e., lower Kirchhoff index implies
higher robustness, and vice versa [young2015new], [ellens2011effective],
[siami2013fundamental]. We note that network robustness, as measured by both
of these measures, is a monotonically increasing function of edge additions
[ellens2011effective, wang2010graphs]. Thus, adding edges to a graph improves
its robustness to failures and noise.

##  III Designing Controllable and Robust Networks

In this section, we will design strong structurally controllable and maximally
robust networks for a given number of nodes $N$ and number of leaders $N_{L}$.
We will present three designs, each with different characteristics and
performances. In the next section, we provide a distributed way of
constructing the proposed graphs; wherein all the nodes follow a set of local
rules (graph grammars) to make connections with their neighbors to achieve the
desired graphs.

###  III-A Network Design 1

We know that a graph with a single leader can only be completely controllable
if the graph is a path graph with the leader node being one of the end nodes.
Therefore, given $N_{L}$ number of leaders, and $N=(N_{L}\times D)$ number of
total nodes, where $D$ is the diameter, we construct a graph $\mathcal{G}_{1}$
with these specifications. For $\mathcal{G}_{1}$, we create $N_{L}$ path
graphs, each with a diameter $D-1$. Also, the end node of each path is a
leader. We then make all leaders pair-wise adjacent, thus, inducing a complete
graph among leaders. We describe this construction formally below. Consider
the following vertex set for graph $\mathcal{G}_{1}$:

$V=\\{\ell_{i}\\}\cup\\{u_{i,j}\\}$,

where $i\in\\{1,2,\dots,k\\}$ and $j\in\\{1,2,\dots,D-1\\}$. Vertices with
label $\\{\ell_{1},\ell_{2},\dots,\ell_{k}\\}$ are leaders and the rest
$\\{u_{1,1},\dots,u_{i,j},\dots,u_{k,D-1}\\}$ are followers. Connect the
vertices in the following manner:

  * •

All the leaders $\ell_{i}$ have a link between them and generate a complete
graph among them.

  * •

For all $i\in\\{1,2,\dots,k\\}$, there exists a link between $\ell_{i}$ and
$u_{i,1}$.

  * •

For all $i\in\\{1,2,\dots,k\\}$ and $j\in\\{1,2,\dots,D-2\\}$, there is a link
between $u_{i,j}$ and $u_{i,j+1}$.

Figure 2 illustrates the construction of Graph $\mathcal{G}_{1}$.

Figure 2: Graph $\mathcal{G}_{1}$ with $N_{L}$ number of leaders, $D$ diameter
and $N=(N_{L}\times D)$ nodes.

The graph constructed above is strong structurally controllable with diameter
$D-1$. Note that we can add edges to the graph $\mathcal{G}_{1}$ without
affecting both, SSC of the graph and the distances between leaders and
remaining nodes. Adding edges is useful to increase the graph robustness.

Adding Maximum Edges to Graph $\mathcal{G}_{1}$: Adding edges reduces
Kirchhoff index and increases the algebraic connectivity, thus, improving
robustness [ellens2011effective]. We refer the maximally robust graph
constructed from $\mathcal{G}_{1}$ as $\bar{\mathcal{G}}_{1}$. Note that the
addition of edges must not deteriorate SSC. We propose the following addition
of edges for the construction of $\bar{\mathcal{G}}_{1}$:

  * •

All the leaders $\ell_{i}$ has an edge with $u_{q,1}$ $\forall q<i$, where
$i,q\in\\{1,2,\dots,k\\}$.

  * •

Similarly, all the nodes in $u_{i,j}$ has an edge with nodes in $u_{q,j+1}$
$\forall q<i$, where $i,q\in\\{1,2,\dots,k\\}$ and $j\in\\{1,2,\dots,D-2\\}$.

  * •

Also, for a fixed $j$, all nodes in $u_{i,j}$ generate a complete graph, where
$i\in\\{1,2,\dots,k\\}$ and $j\in\\{1,2,\dots,D-1\\}$

Figure 3 illustrates the construction of $\bar{\mathcal{G}_{1}}$ from
$\mathcal{G}$. The newly added edges are shown in blue and orange.

Figure 3: Graph $\bar{\mathcal{G}}_{1}$ with maximal edges.

###### Lemma 3.1

The leader set $\\{\ell_{1},\ell_{2},\cdots,\ell_{N_{L}}\\}$ is a ZFS of
$\bar{\mathcal{G}}_{1}$ (described above) with $N$ nodes and $D$ diameter.