A Scalable Distributed Dynamical Systems Approach to Learn the Strongly Connected Components and Diameter of Networks
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 dependent on the number of vertices in the network, the (finite) diameter of the network, and 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.
E. A. Reed, G. Ramos, P. Bogdan and S. Pequito, "A Scalable Distributed Dynamical Systems Approach to Learn the Strongly Connected Components and Diameter of Networks," in IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 3099-3106, May 2023, doi: 10.1109/TAC.2022.3209446
Emily Reed. (2023). ereed1272/distributedDirectedGraphAlgos: distributedDirectedGraphAlgos (publish). Zenodo. https://doi.org/10.5281/zenodo.8208825
Electrical & Computer Engineering
-
Address
Texas Tech University, Box 43102, 910 Boston Ave., Lubbock, TX 79409 -
Phone
806.742.3533 -
Email
ece@ttu.edu