Fast Sequential Creation of Random Realizations of Degree Sequences. Issue 3 (3rd May 2016)

• Record Type: Journal Article
• Authors: Cloteaux, Brian
• Is Part Of: Internet mathematics. Volume 12:Issue 3(2016)
• Page Start: 205
• Page End: 219
• Publication Date: 2016-05-03
• Subjects: Internet -- Mathematics -- Periodicals; Information networks -- Mathematics -- Periodicals; Information networks; Internet; Periodicals; 004.0151
• DOI: 10.1080/15427951.2016.1164768
• Languages: English
• ISSNs: 1944-9488

Abstract

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.