  In this paper, we consider a network of agents with Laplacian dynamics, and
study the problem of improving network robustness by adding a maximum number of
edges within the network while preserving a lower bound on its strong
structural controllability (SSC) at the same time. Edge augmentation increases
network's robustness to noise and structural changes, however, it could also
deteriorate network controllability. Thus, by exploiting relationship between
network controllability and distances between nodes in graphs, we formulate an
edge augmentation problem with a constraint to preserve distances between
certain node pairs, which in turn guarantees that a lower bound on SSC is
maintained even after adding edges. In this direction, first we choose a node
pair and maximally add edges while maintaining the distance between selected
nodes. We show that an optimal solution belongs to a certain class of graphs
called clique chains. Then, we present an algorithm to add edges while
preserving distances between a certain collection of nodes. Further, we present
a randomized algorithm that guarantees a desired approximation ratio with high
probability to solve the edge augmentation problem. Finally, we evaluate our
results on various networks.
