Generating random regular graphs
Generating random regular graphs (scientific article; zbMATH DE number 5150179)
Fix a pair of positive integers \(1\leq d<n\) and let \(S(n,d)\) be the set of all simple \(d\)-regular graphs on a set of \(n\) vertices. The uniform random \(d\)-regular graph \(G_{n,d}\) is obtained by sampling with respect to the uniform distribution from \(S(n,d)\). The probability of each simple \(d\)-regular graph is thus \(1/| S(n,d)|\). Since \(nd\) is twice the number of edges in \(G_{n,d}\), we always assume that \(nd\) is even. Despite an extensive study, a very fundamental, and perhaps practically the most important, question concerning random regular graphs has not yet been answered in a satisfactory way: Question: How do we generate a uniform random regular graph? The paper under review presents a contribution to the answer of this question. The authors analyze an algorithm introduced by \textit{A. Steger} and \textit{N. Wormald} [Comb. Probab. Comput. 8, 377--396 (1999; Zbl 0935.05082)] and prove that it produces an asymptotically uniform random \(d\)-regular graph in time \(O(nd^2)\) for \(d\) and \(n\) satisfying \(d=O(n^{1/3-\epsilon})\) as \(n\to\infty\), where \(\epsilon\) is a positive constant. This confirms a conjecture of \textit{N. Wormald} [Lond. Math. Soc. Lect. Note Ser. 267, 239--298 (1999; Zbl 0935.05080)]. The method of proof is based on a recently developed concentration inequality which can be applied to functions with large Lipschitz coefficients.
- Generating random regular graphs
- Generating Random Regular Graphs Quickly
- A sequential algorithm for generating random graphs
- Uniform generation of random regular graphs
- Uniform generation of random regular graphs of moderate degree
- Fast uniform generation of random graphs with given degree sequences
- A Sequential Algorithm for Generating Random Graphs
- Generating Random Unlabelled Graphs
- Efficient and simple generation of random simple connected graphs with prescribed degree sequence
- Computing and Combinatorics
- Rate of convergence of the short cycle distribution in random regular graphs generated by pegging
- The evolution of the min-min random graph process
- The switch Markov chain for sampling irregular graphs and digraphs
- Out-of-equilibrium dynamics and excess volatility in firm networks
- The average distance and the diameter of dense random regular graphs
- Preferential attachment without vertex growth: emergence of the giant component
- Uniform generation of spanning regular subgraphs of a dense graph
- Efficient importance sampling for binary contingency tables
- Mixing time of the switch Markov chain and stable degree sequences
- Robustness of random graphs based on graph spectra
- Generating Random Networks and Graphs
- Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
- On the asymmetry of random regular graphs and random graphs
- Random Star Processes
- Generating random networks without short cycles
- Uniform generation of random regular graphs
- Generating Outerplanar Graphs Uniformly at Random
- Generating random regular graphs
- Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
- Approximate sampling and counting of graphs with near-regular degree intervals
- Random Schreier graphs as expanders
This page was built for publication: Generating random regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5899329)
