Uniform sampling of digraphs with a fixed degree sequence
From MaRDI portal
Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- The switch Markov chain for sampling irregular graphs and digraphs
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Constructing and sampling directed graphs with given degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
- The switch Markov chain for sampling irregular graphs (extended abstract)
Cites work
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A remark on the existence of finite graphs
- A sequential algorithm for generating random graphs
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
- Algorithms for constructing graphs and digraphs with given valences and factors
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Combinatorial Properties of Matrices of Zeros and Ones
- Generating random regular graphs
- Generating Random Regular Graphs Quickly
- scientific article; zbMATH DE number 420886 (Why is no real title available?)
- scientific article; zbMATH DE number 1334601 (Why is no real title available?)
- scientific article; zbMATH DE number 1089130 (Why is no real title available?)
- scientific article; zbMATH DE number 878897 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Network Analysis
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the degrees of the vertices of a directed graph
- On the realization of a (p,s)-digraph with prescribed degrees
- Sampling binary contingency tables with a greedy start
- Sampling Regular Graphs and a Peer-to-Peer Network
- The Factors of Graphs
- Uniform generation of random regular graphs of moderate degree
Cited in
(21)- The switch Markov chain for sampling irregular graphs and digraphs
- The mixing time of switch Markov chains: a unified approach
- Mixing time of the switch Markov chain and stable degree sequences
- Uniform random sampling of planar graphs in linear time
- Uniform sampling of directed and undirected graphs conditional on vertex connectivity
- Uniform sampling of bipartite graphs with degrees in prescribed intervals
- The connectivity of graphs of graphs with self-loops and a given degree sequence
- New classes of degree sequences with fast mixing swap Markov chain sampling
- On the swap-distances of different realizations of a graphical degree sequence
- Switching edges to randomize networks : What goes wrong and how to fix it
- On the Complexity of Sampling Vertices Uniformly from a Graph
- Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
- Parallel and I/O-efficient randomisation of massive networks using global curveball trades
- Constructing and sampling directed graphs with given degree sequences
- On random sampling in uniform hypergraphs
- Engineering uniform sampling of graphs with a prescribed power-law degree sequence
- Uniformly sampling random directed hypergraphs with fixed degrees
- Hypercurveball algorithm for sampling hypergraphs with fixed degrees
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
- MCMC conditional maximum likelihood for the two-way fixed-effects logit
- Split digraphs
This page was built for publication: Uniform sampling of digraphs with a fixed degree sequence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3057627)
