News & Events

Subscribe to email list

Please select the email list(s) to which you wish to subscribe.

You are here

Degree distribution of shortest path trees and bias in network sampling algorithms

Tuesday, November 25, 2014 - 11:00
Julia Komjathy
Seminar
Room 4192, Earth Sciences Building

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.