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

Journal article (2023)

Authors

Emily Reed University of Southern California
Guilherme Ramos Universidade do Porto
Paul Bogdan University of Southern California
S.D. Gonçalves Melo Pequito Team Sergio Pequito - Mechanical, Maritime and Materials Engineering
Research Group
Team Sergio Pequito (Mechanical, Maritime and Materials Engineering) (TU Delft)
Copyright: © 2023 Emily A. Reed, Guilherme Ramos, Paul Bogdan, S.D. Gonçalves Melo Pequito
DOI
help_outline
https://doi.org/10.1109/TAC.2022.3209446
Machine learning Geometry Heuristic algorithms Machine learning algorithms Power grids Protocols Distributed algorithms
More Info
expand_more

Published Date

2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Mechanical, Maritime and Materials Engineering

Department

Delft Center for Systems and Control

Research Group

Team Sergio Pequito

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.