Betweenness, a measure of the centrality of a node in a network, is the fraction of shortest paths between node pairs that pass through the node of interest.
Betweenness is a measure of the influence that a node has over the spread of information through the network. However, by counting only shortest paths, the conventional definition of betweenness implicitly assumes that information spreads only along those shortest paths. The conventional definition of betweenness is:
where σs,t is the number of shortest paths between nodes s and t and σs,t(ν) is the number of shortest paths between s and t that pass through node ν.
The Betweenness function uses a hybrid distributed AllPairShortestPath (APSP) algorithm, which executes a single-node shortest path (SNSP) algorithm for each vertex in the graph. By restricting the number of parallel SNSP executions to groups of K vertices, the APSP algorithm enables a trade-off between time and memory usage. (For more information on APSP, see AllPairsShortestPath.)
Assume that N is the number of vertices in the graph, K is the number of vertices that start their SNSP algorithms in parallel, and D is the number of iterations required to complete a single SNSP algorithm. The APSP algorithm completes when N/K of these SNSP algorithms have completed. The hybrid distributed APSP algorithm requires O(D*N/K) iterations and O(N*K) space. In the worst case, D is bounded by the diameter DG of the graph; however, you can specify bound M on the distance between vertices. For unweighted graphs, D <= DG <= M.