A1 Refereed original research article in a scientific journal
Finite-Time Distributed Algorithms for Verifying and Ensuring Strong Connectivity of Directed Networks
Authors: Atman, Made Widhi Surya; Gusrialdi, Azwirman
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Publication year: 2022
Journal: IEEE transactions on network science and engineering
Journal name in source: IEEE Transactions on Network Science and Engineering
Volume: 9
Issue: 6
First page : 4379
Last page: 4392
ISSN: 2327-4697
eISSN: 2334-329X
DOI: https://doi.org/10.1109/TNSE.2022.3200466
Web address : https://doi.org/10.1109/tnse.2022.3200466
Abstract
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.
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.
UTU Research Portal