期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 68, 期 5, 页码 3099-3106出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2022.3209446
关键词
Heuristic algorithms; Distributed algorithms; Protocols; Power grids; Machine learning algorithms; Machine learning; Geometry; Algorithms; consensus control; control design; control engineering; directed graphs; distributed algorithms; machine learning algorithms
In this article, a scalable distributed solution is proposed for finding strongly connected components (SCCs) and the diameter of a directed network. The solution leverages dynamical consensus-like protocols and has a time complexity of O(NDd(max) (in-degree)), where N is the number of vertices, D is the network diameter, and d(max) (in-degree) is the maximum in-degree. It is proven that the algorithm terminates in D + 2 iterations, allowing the retrieval of the finite network diameter. Exhaustive simulations demonstrate the outperformance of the proposed algorithm on various random 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 of O(NDd(max) (in-degree)), where N is the number of vertices in the network, D is the (finite) diameter of the network, and d(max) (in-degree) 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 Erdo?s-Renyi, Barabasi-Albert, and Watts-Strogatz networks.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据