Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Fast Sequential Creation of Random Realizations of Degree Sequences

Published

Author(s)

Brian D. Cloteaux

Abstract

We examine the problem of creating a 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 can guarantee termination while achieving speed comparable to the MCMC method.
Citation
Internet Mathematics
Volume
12
Issue
3

Keywords

random graph, degree sequence

Citation

Cloteaux, B. (2016), Fast Sequential Creation of Random Realizations of Degree Sequences, Internet Mathematics, [online], https://doi.org/10.1080/15427951.2016.1164768 (Accessed March 28, 2024)
Created March 24, 2016, Updated November 10, 2018