Back to Search
Start Over
DC-RST: a parallel algorithm for random spanning trees in network analytics
- Source :
- Applied Network Science, Vol 9, Iss 1, Pp 1-16 (2024)
- Publication Year :
- 2024
- Publisher :
- SpringerOpen, 2024.
-
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.
Details
- Language :
- English
- ISSN :
- 23648228
- Volume :
- 9
- Issue :
- 1
- Database :
- Directory of Open Access Journals
- Journal :
- Applied Network Science
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.9dc9528a604241b2ebcd9eedb5d121
- Document Type :
- article
- Full Text :
- https://doi.org/10.1007/s41109-024-00613-7