Edge Augmentation with Controllability Constraints in Directed Laplacian Networks

Waseem Abbas, Mudassir Shabbir, Yasin Yazicioglu, Xenofon Koutsoukos

Research output: Contribution to journalArticlepeer-review

Abstract

In this letter, we study the maximum edge augmentation problem in directed Laplacian networks to improve their robustness while preserving lower bounds on their strong structural controllability (SSC). Since adding edges could adversely impact network controllability, the main objective is to maximally densify a given network by selectively adding missing edges while ensuring that SSC of the network does not deteriorate beyond certain levels specified by the SSC bounds. We consider two widely used bounds: first is based on the notion of zero forcing (ZF), and the second relies on the distances between nodes in a graph. We provide an edge augmentation algorithm that adds the maximum number of edges in a graph while preserving the ZF-based bound, and also derive a closed-form expression for the exact number of edges added to the graph. Then, we examine the edge augmentation while preserving the distance-based bound and present a randomized algorithm that guarantees an $\alpha $ -approximate solution with high probability. Finally, we numerically evaluate and compare these edge augmentation solutions.

Original languageEnglish (US)
Article number9454506
Pages (from-to)1106-1111
Number of pages6
JournalIEEE Control Systems Letters
Volume6
DOIs
StateSubmitted - Jan 1 2022

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

Keywords

  • Edge augmentation
  • Graph distances
  • Structural controllability
  • Zero forcing

Fingerprint

Dive into the research topics of 'Edge Augmentation with Controllability Constraints in Directed Laplacian Networks'. Together they form a unique fingerprint.

Cite this