Fast uniform generation of random graphs with given degree sequences

DOI10.1002/RSA.21004MaRDI QIDQ6074660zbMATH OpenOpenAlexFDO

Authors Andrii Arman, Pu Gao, Nicholas Wormald

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.03446

zbMATH Keywords

random graphsrandomized generation algorithmsrejection sampling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Abstract: In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that $Delt{a}^4=O(m)$, where $Delta$ is the maximal degree and $m$ is the number of edges,the algorithm runs in expected time $O(m)$. Our algorithm significantly improves the previously most efficient uniform sampler, which runs in expected time $O(m^{2}Delt{a}^2)$ for the same family of degree sequences. Our method uses a novel ingredient which progressively relaxes restrictions on an object being generated uniformly at random, and we use this to give fast algorithms for uniform sampling of graphs with other degree sequences as well. Using the same method, we also obtain algorithms with expected run time which is (i) linear for power-law degree sequences in cases where the previous best was $O(n^{4.081})$, and (ii) $O(nd+d^4)$ for $d$-regular graphs when $d=o(sqrtn)$, where the previous best was $O(n{d}^3)$.

Recommendations

• A sequential algorithm for generating random graphs
• A Sequential Algorithm for Generating Random Graphs
• Uniform generation of random graphs with power-law degree sequences
• Fast uniform generation of regular graphs
• Uniform generation of random regular graphs of moderate degree

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A sequential algorithm for generating random graphs
• Fast uniform generation of regular graphs
• Generating random regular graphs
• Generating Random Regular Graphs Quickly
• scientific article; zbMATH DE number 3654183 (Why is no real title available?)
• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• scientific article; zbMATH DE number 3435482 (Why is no real title available?)
• Sampling Regular Graphs and a Peer-to-Peer Network
• The asymptotic number of labeled graphs with given degree sequences
• The switch Markov chain for sampling irregular graphs (extended abstract)
• Uniform generation of random graphs with power-law degree sequences
• Uniform generation of random regular graphs
• Uniform generation of random regular graphs of moderate degree

Cited in

(26)

• An algorithm generating random graphs with power law degree distributions
• Sampling k-partite graphs with a given degree sequence
• Generating connected acyclic digraphs uniformly at random
• A linear-time algorithm for sampling graphs with given degrees
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• Efficient generation of networks with given expected degrees
• Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
• A Sequential Algorithm for Generating Random Graphs
• Generating Practical Random Hyperbolic Graphs in Near-Linear Time and with Sub-Linear Memory
• Uniform generation of random graphs with power-law degree sequences
• Efficient and simple generation of random simple connected graphs with prescribed degree sequence
• Moments of uniform random multigraphs with fixed degree sequences
• Generating graphs randomly
• Constructing and sampling directed graphs with given degree sequences
• Generating stationary random graphs on ℤ with prescribed independent, identically distributed degrees
• Computing and Combinatorics
• Fast sequential creation of random realizations of degree sequences
• Generating random regular graphs
• A sequential algorithm for generating random graphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Engineering uniform sampling of graphs with a prescribed power-law degree sequence
• Linear-time uniform generation of random sparse contingency tables with specified marginals
• Uniform generation of temporal graphs with given degrees
• Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
• Degree-preserving graph dynamics: a versatile process to construct random networks
• Fast uniform generation of regular graphs

This page was built for publication: Fast uniform generation of random graphs with given degree sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074660)