Finding strongly connected components (SCCs) and the diameter of a directed network play a key role in a variety of discrete optimization problems, and subsequently, machine learning and control theory problems. On the one hand, SCCs are used in solving the 2-satisfiability problem, which has applications in clustering, scheduling, and visualization. On the other hand, the diameter has applications in network learning and discovery problems enabling efficient internet routing and searches, as well as identifying faults in the power grid. In this paper, we leverage consensus-based principles to find the SCCs in a scalable and distributed fashion with a computational complexity of O(Ddmaxin−degree) , where D is the (finite) diameter of the network and dmaxin−degree is the maximum in-degree of the network. Additionally, we prove that our algorithm terminates in D+1 iterations, which allows us to retrieve the diameter of the network. We illustrate the performance of our algorithm on several random networks, including Erdö-Rényi, Barabási-Albert, and Watts-Strogatz networks.
more »
« less
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
