2020/01/22 by Pierluigi Crescenzi, Crescenzi, Pierluigi, Pierre Fraigniaud +3 · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Advanced Optical Network Technologies #Complex Network Analysis Techniques #Distributed #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Social and Information Networks (cs.SI) #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2001.08108
openalex publication_date 2020/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
Betweenness centrality is a graph parameter that has been successfully applied to network analysis. In the context of computer networks, it was considered for various objectives, ranging from routing to service placement. However, as observed by Maccari et al. [INFOCOM 2018], research on betweenness centrality for improving protocols was hampered by the lack of a usable, fully distributed algorithm for computing this parameter. We resolve this issue by designing an efficient algorithm for computing betweenness centrality, which can be implemented by minimal modifications to any distance-vector routing protocol based on Bellman-Ford. The convergence time of our implementation is shown to be proportional to the diameter of the network