Fast uniform generation of random graphs with given degree sequences

Andrii Arman, Pu Gao, Nicholas Wormald

Research output: Contribution to journalArticleResearchpeer-review

Abstract

In this paper we provide an algorithm that generates a graph with given degree sequence uniformly at random. Provided that (Formula presented.), where (Formula presented.) 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 (Formula presented.) 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(n4.081), and (ii) O(nd + d4) for d-regular graphs when (Formula presented.), where the previous best was O(nd3).

Original languageEnglish
Pages (from-to)291-314
Number of pages24
JournalRandom Structures and Algorithms
Volume59
Issue number3
DOIs
Publication statusPublished - Oct 2021

Keywords

  • random graphs
  • randomized generation algorithms
  • rejection sampling
  • Fast Uniform Generation of Random Graphs with Given Degree Sequences

    Arman, A., Gao, P. & Wormald, N., 20 Jan 2020, Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019: 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019; Baltimore; United States; 9 November 2019 through 12 November 2019. Piscataway NJ USA: IEEE Computer Society, p. 1371-1379 9 p. 8948622. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

    4 Citations (Scopus)

Cite this