HIV Working Group

Jonathan LarsonDoctoral Student, Department of Biostatistics, Harvard University”Inferring the Minimum Spanning Tree (MST) from a Sample Network”ABSTRACT: Minimum spanning trees (MSTs) have been used by infectious disease researchers 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 the MST of a sample network. We prove that if n nodes (the sample) are selected uniformly at random from a complete graph with N nodes (the population) and i.i.d. edge weights, 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ási-Albert graphs (BA), graphs whose nodes are distributed in R^2 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 graphs are similar. Applied researchers are encouraged to use an edge-weighted random walk to sample nodes so that they maximize the probability that an edge is in the population MST given that it is in the sample MST.Bio: Jonathan Larson is a 5th-year doctoral student in the Department of Biostatistics. His research focuses on statistical inference from network data, with a focus on HIV transmission.