Distributed Articulation Point Identification in Time-Varying Undirected Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912748616548352 |
|---|---|
| author | Xie, Xinye Zheng, Ronghao Zhang, Senlin Liu, Meiqin |
| author_facet | Xie, Xinye Zheng, Ronghao Zhang, Senlin Liu, Meiqin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_04409 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Articulation Point Identification in Time-Varying Undirected Networks Xie, Xinye Zheng, Ronghao Zhang, Senlin Liu, Meiqin Social and Information Networks Systems and Control 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. |
| title | Distributed Articulation Point Identification in Time-Varying Undirected Networks |
| topic | Social and Information Networks Systems and Control |
| url | https://arxiv.org/abs/2512.04409 |