  One of the most fundamental problems in large scale network analysis is to
determine the importance of a particular node in a network. Betweenness
centrality is the most widely used metric to measure the importance of a node
in a network. In this paper, we present a randomized parallel algorithm and an
algebraic method for computing betweenness centrality of all nodes in a
network. We prove that any path-comparison based algorithm cannot compute
betweenness in less than O(nm) time.
