A Scalable Distributed Dynamical Systems Approach to Learn the Strongly Connected Components and Diameter of Networks

Title

A Scalable Distributed Dynamical Systems Approach to Learn the Strongly Connected Components and Diameter of Networks

 Author

Reed, Emily A. (University of Southern California)
Ramos, Guilherme (Universidade do Porto)
Bogdan, Paul (University of Southern California)
Gonçalves Melo Pequito, S.D. (TU Delft Team Sergio Pequito)

Date

2023

 Abstract

Finding strongly connected components (SCCs) and the diameter of a directed network play a key role in a variety of machine learning and control theory problems. In this article, we provide for the first time a scalable distributed solution for these two problems by leveraging dynamical consensus-like protocols to find the SCCs. The proposed solution has a time complexity of O(NDd in-degreemax), where N is the number of vertices in the network,D is the (finite) diameter of the network, and din-degreemax is the maximum in-degree of the network. Additionally, we prove that our algorithm terminates in D+2 iterations, which allows us to retrieve the finite diameter of the network. We perform exhaustive simulations that support the outperformance of our algorithm against the state of the art on several random networks, including Erdős-Rényi, Barabási-Albert, and Watts-Strogatz networks.


 Subject

Distributed algorithms
Geometry
Heuristic algorithms
Machine learning
Machine learning algorithms
Power grids
Protocols

 To reference this document use:

http://resolver.tudelft.nl/uuid:3af26809-578d-4980-a4f0-b39a3808242f

 DOI

https://doi.org/10.1109/TAC.2022.3209446

 Embargo date

2023-03-27

 ISSN

0018-9286

 Source

IEEE Transactions on Automatic Control, 68 (5), 3099-3106

 Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

 Part of collection

Institutional Repository

 Document type

journal article

 Rights

© 2023 Emily A. Reed, Guilherme Ramos, Paul Bogdan, S.D. Gonçalves Melo Pequito
Files
PDF A_Scalable_Distributed_Dy ... tworks.pdf 2.58 MB
Close viewer