  The betweenness centrality (BC) of a node in a network (or graph) is a
measure of its importance in the network. BC is widely used in a large number
of environments such as social networks, transport networks, security/mobile
networks and more. We present an O(n)-round distributed algorithm for computing
BC of every vertex as well as all pairs shortest paths (APSP) in a directed
unweighted network, where n is the number of vertices and m is the number of
edges. We also present O(n)-round distributed algorithms for computing APSP and
BC in a weighted directed acyclic graph (dag). Our algorithms are in the
Congest model and our weighted dag algorithms appear to be the first nontrivial
distributed algorithms for both APSP and BC. All our algorithms pay careful
attention to the constant factors in the number of rounds and number of
messages sent, and for unweighted graphs they improve on one or both of these
measures by at least a constant factor over previous results for both directed
and undirected APSP and BC.
