Papers › Inferring the minimum spanning tree from a sample network
Inferring the minimum spanning tree from a sample network
Jonathan Larson, Jukka-Pekka Onnela
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Minimum spanning trees (MSTs) are used in a variety of fields, from computer science to geography. Infectious disease researchers have used them to infer the transmission pathway of certain pathogens. However, these are often the MSTs of sample networks, not population networks, and surprisingly little is known about what can be inferred about a population MST from a sample MST. We prove that if n nodes (the sample) are selected uniformly at random from a complete graph with N nodes and unique edge weights (the population), the probability that an edge is in the population graph's MST given that it is in the sample graph's MST is n/N. We use simulation to investigate this conditional probability for G(N,p) graphs, Barab\'{a}si-Albert (BA) graphs, graphs whose nodes are distributed in ℝ² according to a bivariate standard normal distribution, and an empirical HIV genetic distance network. Broadly, results for the complete, G(N,p), and normal graphs are similar, and results for the BA and empirical HIV graphs are similar. We recommend that researchers use an edge-weighted random walk to sample nodes from the population so that they maximize the probability that an edge is in the population MST given that it is in the sample MST.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections