Distributed Articulation Point Identification in Time-Varying Undirected Networks

Xinye Xie, Ronghao Zheng, Senlin Zhang, Meiqin LiuarXiv 2025 · DOI · arXiv

Abstract

Identifying articulation points (APs)—nodes whose failure disconnects a network—is critical for assessing network robustness. While centralized algorithms are well-established, distributed and dynamic environments pose significant challenges. This paper introduces a fully distributed, incremental algorithm that identifies APs in time-varying networks without requiring global topology knowledge. By replacing global resets with localized "change flag" propagation and an update-correct consensus mechanism, the approach achieves rapid convergence and preserves node privacy.

Introduction

In network science, biconnectivity is a key metric for robustness, representing a network's ability to remain connected despite a single node failure. Nodes that break this connectivity are termed articulation points or cut vertices. In static, centralized systems, these are easily identified using depth-first search (DFS) algorithms. However, modern networks such as robot swarms, power grids, and social networks are inherently distributed and dynamic.

Figure 1: Visualization of articulation points (red nodes) in a 10-node undirected network.

Existing distributed methods often suffer from high communication overhead because they require a "global reset" whenever an edge is added or deleted. Furthermore, these methods often compromise privacy by requiring nodes to share local connection data. This paper addresses these limitations by proposing an incremental, privacy-preserving framework.

Methodology

The proposed framework utilizes a maximum consensus protocol where nodes maintain local states: a binary reachability vector and a shortest-path distance vector. The core of the system is a three-part incremental update mechanism.

Incremental Update Mechanism

  1. Change Flag Propagation: Upon an edge event (addition or deletion), incident nodes generate a "change flag" containing the event type, involved nodes, and a timestamp. This flag ripples through the network, signaling affected nodes to re-evaluate their states.
  2. Consensus Update Strategy: Nodes employ a modified max-consensus logic. When a flag arrives, the node distinguishes between "historical" reachability and "constraint" reachability (paths potentially broken by the change), preventing the algorithm from stalling on outdated information.
  3. Local State Correction: A "distance difference metric" allows nodes to determine if a local change invalidates their current shortest paths. If a deleted edge was not part of a node's shortest path, the node ignores the change, minimizing unnecessary recalculations.
Figure 2: Timing diagram of the incremental update mechanism showing edge addition and deletion events.

Once local states stabilize, nodes apply a distributed criterion to determine their AP status based solely on distances to immediate neighbors.

Evaluation and Results

The algorithm was evaluated using synthetic simulations:

  • 10-Node Network: Demonstrated recovery from single-edge deletions in 6 communication steps and additions in 5 steps.
  • 20-Node Barabási-Albert (BA) Network: Simulated an "event storm" with high-frequency random changes. While state error increased during the storm, it plummeted to zero immediately once the topology stabilized.

The results confirm that the algorithm successfully identifies the correct set of articulation points in both single-change and high-frequency change scenarios once local stability is reached.

Discussion and Future Work

The "update-correct" philosophy ensures that while intermediate estimates may be inaccurate, the final converged result is guaranteed to be correct. Privacy is maintained because nodes only exchange distance vectors rather than adjacency lists, making global topology reconstruction impossible beyond a 2-hop neighborhood.

Future research will focus on extending this logic to directed networks, where reachability is non-reciprocal, and addressing asynchronous communication challenges such as packet loss and variable delays.

Summary updated

Abstract

Identifying articulation points (APs) is fundamental to assessing the robustness of time-varying networks. In such dynamic environments, topological changes including edge additions and deletions can instantly alter the set of APs, demanding rapid and efficient re-assessment. This paper proposes a fully distributed algorithm for identifying APs and monitoring biconnectivity. Our core contribution is an incremental update protocol. Unlike static methods that require global re-initialization which incurs high communication overhead, our algorithm propagates information from the site of the change, updating only the affected nodes' state values. This approach, which builds upon a maximum consensus protocol, not only ensures convergence to the correct AP set following topological changes but also preserves network privacy by preventing nodes from reconstructing the global topology. We provide rigorous proofs of correctness for this eventual convergence and demonstrate its applicability and efficiency through experiments.
BibTeX
@misc{xie2025distributed,
  author = {Xinye Xie and Ronghao Zheng and Senlin Zhang and Meiqin Liu},
  title = {{Distributed Articulation Point Identification in Time-Varying Undirected Networks}},
  year = {2025},
  eprint = {2512.04409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.04409},
}
Figure