DC-RST: A Parallel Algorithm for Random Spanning Trees in Network Analytics

Abstract The Mantel Test, discovered in the 1960s, determines whether two distance metrics on a graph are related. We describe DC-RST, an algorithm to accelerate a key step of a network science statistical computation associated with DimeCost, an approach that is faster the Mantel Test. DC-RST is a parallel, divide-and-conquer algorithm to compute a random spanning tree of a complete graph on n vertices. Relative to an implementation of Wilson’s sequential random-walk algorithm, on a system with 48 cores, DC-RST was up to 4X faster when first creating random partitions and up to 20X faster without this sub-step. DC-RST is shown to be a suitable replacement for Wilson’s sequential algorithm through a combination of theoretical and statistical results.