A Scalable Distributed Dynamical Systems Approach to Compute the Strongly Connected Components and Diameter of Networks
A Scalable Distributed Dynamical Systems Approach to Compute the Strongly Connected Components and Diameter of Networks
复制标题
计算强连通分量和网络直径的可扩展分布式动力系统方法
DOI：
10.1109/tac.2022.3209446
复制
发表时间：
2022
影响因子：
6.8
通讯作者：
Pequito, Sergio
中科院分区：
文献类型：
--
作者：
Reed, Emily A.;Ramos, Guilherme;Bogdan, Paul;Pequito, Sergio
寻找强连接组件（SCC）和有向网络的直径在各种机器学习和控制理论问题中起着关键作用。在这篇文章中，我们第一次提供了一个可扩展的分布式解决方案，这两个问题，利用动态共识协议来找到SCC。该方法的时间复杂度为，其中是网络的顶点数，是网络的（有限）直径，是网络的最大入度。此外，我们证明了我们的算法终止迭代，这使我们能够检索网络的有限直径。我们进行了详尽的模拟，支持我们的算法对几个随机网络，包括Erdens-Rényi，Barabási-Albert和Watts-Strogatz网络的最先进的性能。
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, whereis the number of vertices in the network,is the (finite) diameter of the network, andis the maximum in-degree of the network. Additionally, we prove that our algorithm terminates initerations, 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.