Simple and Fast Distributed Computation of Betweenness Centrality

Abstract

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

References in corpus (7)

• Statistical mechanics of complex networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Self-similar community structure in organisations
• Universal Behavior of Load Distribution in Scale-free Networks
• Distributed Algorithms for Computation of Centrality Measures in Complex Networks
• Distributed estimation and control of node centrality in undirected asymmetric networks
• Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths