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

Emily A. Reed; Guilherme Ramos; Paul Bogdan; Sergio Pequito

doi:10.1109/TAC.2022.3209446

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

Emily A. Reed, Guilherme Ramos, Paul Bogdan, Sergio Pequito

Team Sergio Pequito

Research output: Contribution to journal › Article › Scientific › peer-review

33 Downloads (Pure)

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.

Original language	English
Pages (from-to)	3099-3106
Journal	IEEE Transactions on Automatic Control
Volume	68
Issue number	5
DOIs	https://doi.org/10.1109/TAC.2022.3209446
Publication status	Published - 2023

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.

Keywords

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

Access to Document

10.1109/TAC.2022.3209446

A_Scalable_Distributed_Dynamical_Systems_Approach_to_Learn_the_Strongly_Connected_Components_and_Diameter_of_NetworksFinal published version, 2.48 MB

Cite this

@article{3af26809578d4980a4f0b39a3808242f,

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

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{\H o}s-R{\'e}nyi, Barab{\'a}si-Albert, and Watts-Strogatz networks.",

keywords = "Distributed algorithms, Geometry, Heuristic algorithms, Machine learning, Machine learning algorithms, Power grids, Protocols",

author = "Reed, {Emily A.} and Guilherme Ramos and Paul Bogdan and Sergio Pequito",

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.",

year = "2023",

doi = "10.1109/TAC.2022.3209446",

language = "English",

volume = "68",

pages = "3099--3106",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "IEEE",

number = "5",

}

TY - JOUR

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

AU - Reed, Emily A.

AU - Ramos, Guilherme

AU - Bogdan, Paul

AU - Pequito, Sergio

N1 - 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.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - Distributed algorithms

KW - Geometry

KW - Heuristic algorithms

KW - Machine learning

KW - Machine learning algorithms

KW - Power grids

KW - Protocols

UR - http://www.scopus.com/inward/record.url?scp=85139496191&partnerID=8YFLogxK

U2 - 10.1109/TAC.2022.3209446

DO - 10.1109/TAC.2022.3209446

M3 - Article

AN - SCOPUS:85139496191

SN - 0018-9286

VL - 68

SP - 3099

EP - 3106

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 5

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this