Fast Sequential Creation of Random Realizations of Degree Sequences. Issue 3 (3rd May 2016) - Cloteaux, Brian
Abstract: We examine the problem of creating random realizations of very large degree sequences. While fast in practice, the Markov chain Monte Carlo (MCMC) method for selecting a realization has limited usefulness for creating large graphs because of memory constraints. Instead, we focus on sequential importance sampling (SIS) schemes for random graph creation. A difficulty with SIS schemes is assuring that they terminate in a reasonable amount of time. We introduce a new sampling method where we guarantee termination while achieving speed comparable to the MCMC method.