Sampling Regular Graphs and a Peer-to-Peer Network
From MaRDI portal
Abstract: In [Combinatorics, Probability and Computing 16 (2007), 557 - 593, Theorem 1] we proved a polynomial-time bound on the mixing rate of the switch chain for sampling d-regular graphs. This corrigendum corrects a technical error in the proof. In order to fix the error, we must multiply the bound on the mixing time by a factor of d^8 .
Recommendations
Cited in
(55)- Sampling Edge Covers in 3-Regular Graphs
- A triangle process on regular graphs
- Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
- Sampling k-partite graphs with a given degree sequence
- Connectivity of random regular graphs generated by the pegging algorithm
- Lifted algorithms for symmetric weighted first-order model sampling
- Uniform generation of spanning regular subgraphs of a dense graph
- The contact process on dynamic regular graphs: subcritical phase and monotonicity
- Uniform generation of random regular graphs
- Rejection sampling of bipartite graphs with given degree sequence
- scientific article; zbMATH DE number 1743766 (Why is no real title available?)
- Regularized modified log-Sobolev inequalities and comparison of Markov chains
- Configuring random graph models with fixed degree sequences
- Linear-time uniform generation of random sparse contingency tables with specified marginals
- The mixing time of switch Markov chains: a unified approach
- A survey of discrete methods in (algebraic) statistics for networks
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Expansion and flooding in dynamic random networks with node churn
- Degree-preserving graph dynamics: a versatile process to construct random networks
- A sequential algorithm for generating random graphs
- Sampling regular graphs and a peer-to-peer network
- Half-graphs, other non-stable degree sequences, and the switch Markov chain
- Approximate sampling of graphs with near-P-stable degree intervals
- Mixing time of the swap Markov chain and \(P\)-stability
- Uniformly sampling random directed hypergraphs with fixed degrees
- Exact sampling of graphs with prescribed degree correlations
- A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
- Triangle switches: irreducibility and mixing
- Towards communication-efficient Peer-to-Peer networks
- Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
- Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
- Mixing time of the switch Markov chain and stable degree sequences
- Approximate sampling and counting of graphs with near-regular degree intervals
- Constructing and sampling directed graphs with given degree sequences
- Hypercurveball algorithm for sampling hypergraphs with fixed degrees
- On the bias of traceroute sampling
- Sampling Random Graphs with Specified Degree Sequences
- Expansion properties of a random regular graph after random vertex deletions
- Scalable Uniform Graph Sampling by Local Computation
- Fast uniform generation of random graphs with given degree sequences
- Sampling contingency tables
- The phase transition of the voter model on evolving scale-free networks
- Uniform sampling of digraphs with a fixed degree sequence
- Pegging graphs yields a small diameter
- The contact process over a dynamical d-regular graph
- The switch Markov chain for sampling irregular graphs and digraphs
- On the bias of traceroute sampling
- Rapid mixing of the switch Markov chain for 2-class joint degree matrices
- The flip Markov chain and a randomising P2P protocol
- Sampling hypergraphs with given degrees
- Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
- Fast sequential creation of random realizations of degree sequences
- How to determine if a random graph with a fixed degree sequence has a giant component
- The flip Markov chain for connected regular graphs
This page was built for publication: Sampling Regular Graphs and a Peer-to-Peer Network
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5437233)
