A sequential algorithm for generating random graphs
From MaRDI portal
Publication:603928
DOI10.1007/s00453-009-9340-1zbMath1198.05138arXivcs/0702124OpenAlexW3106076975MaRDI QIDQ603928
Amin Saberi, Mohsen Bayati, Jeong Han Kim
Publication date: 8 November 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0702124
Related Items
State-Dependent Kernel Selection for Conditional Sampling of Graphs, Mixing time of the switch Markov chain and stable degree sequences, Fast uniform generation of random graphs with given degree sequences, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Negative examples for sequential importance sampling of binary contingency tables, The switch Markov chain for sampling irregular graphs and digraphs, Computing Minimum k-Connected m-Fold Dominating Set in General Graphs, Rejection sampling of bipartite graphs with given degree sequence, Sampling hypergraphs with given degrees, Configuring Random Graph Models with Fixed Degree Sequences, Sampling for Conditional Inference on Network Data, Uniform Sampling of Digraphs with a Fixed Degree Sequence, Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs, Bootstrapping on undirected binary networks via statistical mechanics, Generating Random Networks Without Short Cycles, Uniform Generation of Random Regular Graphs, Sampling \(k\)-partite graphs with a given degree sequence, Uniform generation of spanning regular subgraphs of a dense graph, A triangle process on regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast uniform generation of regular graphs
- Random generation of combinatorial structures from a uniform distribution
- Approximate counting, uniform generation and rapidly mixing Markov chains
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- The asymptotic number of labeled graphs with given degree sequences
- Relaxing the uniformity and independence assumptions using the concept of fractal dimension
- Connected components in random graphs with given expected degree sequences
- Sandwiching random graphs: universality between random graph models
- Negative examples for sequential importance sampling of binary contingency tables
- Efficient importance sampling for binary contingency tables
- Examples comparing importance sampling and the Metropolis algorithm
- A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
- Mathematics and Computer Science: Coping with Finiteness
- Uniform generation of random regular graphs of moderate degree
- Concentration of non‐Lipschitz functions and applications
- A critical point for random graphs with a given degree sequence
- Generating Random Regular Graphs Quickly
- On Brooks' Theorem for Sparse Graphs
- Sampling Regular Graphs and a Peer-to-Peer Network
- Sequential Monte Carlo Methods for Statistical Analysis of Tables
- Generating random regular graphs
- Sampling binary contingency tables with a greedy start
- Concentration of multivariate polynomials and its applications
