A sequential algorithm for generating random graphs

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

zbMATH Keywords

random graphssequential importance samplingFPRAS

Mathematics Subject Classification ID

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

Related Items (19)

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

This page was built for publication: A sequential algorithm for generating random graphs