1. DC-RST: a parallel algorithm for random spanning trees in network analytics
- Author
-
Luke Henke and Dinesh Mehta
- Subjects
Wilson’s algorithm ,Mantel test ,Dimecost ,Applied mathematics. Quantitative methods ,T57-57.97 - Abstract
Abstract The Mantel Test, discovered in the 1960s, determines whether two distance metrics on a network are related. More recently, DimeCost, an equivalent test with improved computational complexity, was proposed. It was based on computing a random spanning tree of a complete graph on n vertices—the spanning tree was computed using Wilson’s random walk algorithm. In this paper, we describe DC-RST, a parallel, divide-and-conquer random walk algorithm to further speed up this computation. Relative to 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 the Mantel and DimeCost tests through a combination of theoretical and statistical results.
- Published
- 2024
- Full Text
- View/download PDF