A scalable distributed dynamical systems approach to compute the strongly connected components and diameter of networks

Emily A. Reed, Guilherme Ramos, Paul Bogdan, Sérgio PequitoarXiv 2021 · arXiv

Introduction

In the field of network science, identifying the structural properties of large-scale directed graphs is fundamental to understanding system behavior. Two of the most critical metrics are Strongly Connected Components (SCCs)—sub-networks where every node is mutually reachable—and the network diameter ($D$), defined as the longest shortest path between any two nodes. These metrics are essential for optimizing routing protocols, assessing infrastructure vulnerability, and solving complex scheduling problems.

Traditional algorithms for these tasks, such as Tarjan’s or Kosaraju’s for SCCs and Floyd-Warshall for diameter, are primarily centralized. They require a global view of the network topology, which creates a significant computational bottleneck as datasets scale into millions or billions of nodes. This paper proposes a novel distributed approach that leverages principles from control theory—specifically max-consensus dynamics—to compute both SCCs and the network diameter simultaneously using only local neighbor interactions.

Methodology: Algorithm 1

The proposed algorithm treats the network as a discrete-time dynamical system. Unlike centralized methods, each node in this distributed framework operates based solely on information received from its immediate in-neighbors.

Max-Consensus Dynamics

The core mechanism is a max-consensus-like update rule. Each node maintains and updates a set of identifiers representing the nodes that can reach it. The process follows these steps:

  1. Reachability Tracking: In each iteration, nodes broadcast their reachability sets to their neighbors.
  2. Set Aggregation: Nodes update their own sets by taking the union of their current set and the sets received from neighbors.
  3. SCC Identification: By comparing the local reachability information with that of neighbors, nodes can mathematically determine their membership within a specific SCC.

Convergence and Diameter Retrieval

A significant theoretical contribution of this work is the proof that the algorithm converges in exactly $D+1$ iterations. This creates a dual-purpose mechanism: while the nodes are identifying SCCs, the network is implicitly calculating its own diameter. By monitoring the number of iterations until the reachability sets stabilize (i.e., no new information is received), the system "discovers" the global diameter without requiring a central coordinator.

Experimental Evaluation

To validate the scalability and efficiency of the approach, the authors evaluated the algorithm across three standard synthetic network models:

  • Erdős-Rényi (ER): Representing purely random connectivity.
  • Barabási-Albert (BA): Representing scale-free networks common in social and internet structures.
  • Watts-Strogatz (WS): Representing small-world networks with high local clustering.

Tests were conducted on networks ranging from 100 to 500 nodes to observe performance scaling relative to node count and edge density.

Key Results and Insights

The distributed approach demonstrates several advantages over state-of-the-art centralized algorithms:

  • Computational Complexity: The time complexity for each node is $O(D \cdot d_{in}^{max})$, where $d_{in}^{max}$ is the maximum in-degree. In sparse, small-world networks where the diameter is relatively small, this represents a significant improvement over global methods.
  • Comparative Performance: The algorithm consistently outperformed Kosaraju’s algorithm for SCC identification as network size increased. For diameter calculation, it significantly surpassed the $O(|V|^3)$ complexity of the Floyd-Warshall algorithm.
  • Predictable Termination: The rigorous proof of termination at $D+1$ steps provides a reliable stopping criterion, which is often a challenge in distributed computing.

Discussion and Future Directions

The integration of control theory (consensus dynamics) with combinatorial graph problems offers a robust framework for decentralized network analysis. By relying only on local knowledge, the algorithm is inherently resilient and well-suited for ad-hoc or evolving networks where a global map is unavailable.

However, certain challenges remain. The communication overhead—specifically the size of the ID sets being passed between nodes—could become a factor in extremely large-scale deployments. Future research may focus on optimizing these data structures or extending the framework to time-varying networks where edges are dynamic. Additionally, testing the algorithm on massive real-world datasets, such as global social graphs or national power grids, will be essential to further validate its practical utility.

Summary updated

Abstract

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 $\mathcal{O}\left(Dd_{\text{in-degree}}^{\max}\right)$, where $D$ is the (finite) diameter of the network and $d_{\text{in-degree}}^{\max}$ 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\H{o}s-R\'enyi, Barab\'asi-Albert, and \mbox{Watts-Strogatz} networks.
BibTeX
@misc{reed2021scalable,
  author = {Emily A. Reed and Guilherme Ramos and Paul Bogdan and Sérgio Pequito},
  title = {{A scalable distributed dynamical systems approach to compute the strongly connected components and diameter of networks}},
  year = {2021},
  eprint = {2105.10229},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.10229},
}
Figure