Uniform Generation of Random Regular Graphs of Moderate Degree

By Brendan D. McKay, N. Wormald. 1990

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Subgraphs of random graphs with specified degrees (2011, methodology): “For fixed or very slowly increasing degree, the counts of fixed length cycles are asymptotically Poisson and independent, as shown by Bollobás [2] and Wormald [32].”
Generating Simple Random Graphs with Prescribed Degree Distribution (2006, methodology): “However, the price one has to pay for this is a more complicated algorithm and more restrictive assumptions about the degree distribution (the McKay and Wormald criterion corresponds to the degree distribution having moments of order 4 + ǫ ).”
A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees (2011, methodology): “There is also an interesting earlier algorithm by McKay and Wormald [53] based on the pairing model.”
Jellyfish: Networking Data Centers Randomly (2011, methodology): “This is a complex problem in graph theory [29]; however, a simple procedure produces “sufficiently uniform” random graphs which empirically have the desired performance properties.”
The Role of Network Topology for Distributed Machine Learning (2019, methodology): “7The graphs have been generated using the NetworkX implementation of the algorithm in [21].”
Exact sampling and counting for fixed-margin matrices (2013, methodology): “McKay and Wormald (1990) presented an intriguing randomized algorithm for exact uniform sampling from the set of binary matrices with margins p,q, provided that all of the margins are sufficiently small.”