Degree distribution of shortest path trees and bias in network sampling algorithms
In this talk, we investigate the degree distribution of shortest path trees of various weighted network models. The aim of many empirical studies is to determine the degree distribution of a network with unknown structure by using trace-route sampling. We derive the limiting degree distribution of the shortest path tree from a single source on various random network models with edge weights: the configuration model and r-regular graphs with i.i.d. power law degrees and i.i.d. edge weights, the complete graph with edge weights that are powers of i.i.d. exponential random variables. We use these results to shed light on an empirically observed bias in network sampling methods.