Finite-Time Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks

Research output: Contribution to journalArticleScientificpeer-review

9 Downloads (Pure)


The strong connectivity of a directed graph associated with the communication network topology is crucial in ensuring the convergence of many distributed estimation/control/optimization algorithms. However, the assumption on the network's strong connectivity may not always be satisfied in practice. In addition, information on the overall network topology is often not available, e.g., due to privacy concerns or geographical constraints which calls for a distributed algorithm. This paper aims to fill a crucial gap in the literature due to the absence of a fully distributed algorithm to verify and ensure in finite-time the strong connectivity of a directed network. Specifically, inspired by the maximum consensus algorithm we propose distributed algorithms that enable individual node in a networked system to verify the strong connectivity of a directed graph and further, if necessary, augment a minimum number of new links to ensure the directed graph's strong connectivity. The proposed distributed algorithms are implemented without requiring information of the overall network topology and are scalable as they only require finite storage and converge in finite number of steps. Furthermore, the algorithms also preserve the privacy in terms of the overall network's topology. Finally, the proposed distributed algorithms are demonstrated and evaluated via numerical results.
Original languageEnglish
Pages (from-to)4379 - 4392
JournalIEEE Transactions on Network Science and Engineering
Issue number6
Early online date2022
Publication statusPublished - 2022
Publication typeA1 Journal article-refereed

Publication forum classification

  • Publication forum level 1


Dive into the research topics of 'Finite-Time Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks'. Together they form a unique fingerprint.

Cite this