System-Wide Termination in Distributed Betweenness Centrality Computation

[2607.29474] System-Wide Termination in Distributed Betweenness Centrality Computation Skip to main content Search Submit Donate Log in Computer Science > Distributed, Parallel, and Cluster Computing arXiv:2607.29474 (cs) [Submitted on 31 Jul 2026 ( v1 ), last revised 22 Aug 2026 (this version, v2)] Title: System-Wide Termination in Distributed Betweenness Centrality Computation Authors: Siamak Abdi , Lucia Cavallaro , Giuseppe Di Fatta View PDF HTML (experimental) Abstract: Computing betweenness centrality on large networks is inherently expensive, as it requires aggregating shortest-path dependencies across all pairs of vertices and becomes increasingly difficult to scale as network size grows. Scalable distributed algorithms can facilitate such computations, particularly when centralised processing is not feasible, and message exchanges must be carefully controlled, for example, in bandwidth-limited or very large-scale networks. However, existing distributed betweenness centrality implementations do not integrate a lightweight, system-wide termination detector. As a consequence, this can lead to extra messaging after local convergence or, if misconfigured, premature stops. In this work, a lightweight, system-wide global termination detection algorithm for this task is presented. The proposed method enables vertices to decide locally when the overall system has converged. The method is evaluated against a local stopping strategy in which vertices terminate individually once their own estimates stabilise. To compare these two approaches, namely global termination detection and local stopping, a custom Python simulator is implemented, and both approaches are tested on synthetic (Erdos-Renyi and geometric) and real (Email and Road) network topologies. Our results show that system-wide termination detection lets vertices stop safely after detecting global convergence, as indicated by zero final error in the evaluated networks, rather than stopping independently based only on local convergence. The local stopping approach, on the other hand, results in premature termination and some errors on heterogeneous networks. This work emphasises the need for coordinated halting in distributed centrality computation. Comments: License updated; manuscript unchanged Subjects: Distributed, Parallel, and Cluster Computing (cs.DC) Cite as: arXiv:2607.29474 [cs.DC] (or arXiv:2607.29474v2 [cs.DC] for this version) https://doi.org/10.48550/arXiv.2607.29474 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Siamak Abdi [ view email ] [v1] Fri, 31 Jul 2026 14:37:53 UTC (884 KB) [v2] Sat, 22 Aug 2026 18:49:55 UTC (884 KB) Full-text links: Access Paper: View PDF HTML (experimental) TeX Source view license Current browse context: cs.DC < prev | next > new | recent | 2026-07 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• System-Wide Termination in Distributed Betweenness Centrality Computation#665890
• System-Wide Termination in Distributed Betweenness Centrality Computation#422221
• SDG Harmonized Global Dataflow#21759
• Core Based Trees (CBT) Multicast Routing Architecture#136900
• Balancing Generality and Specialization: A Survey on AI Datacenter Hardware Architecture#1063040