Uniform sampling of digraphs with a fixed degree sequence
From MaRDI portal
Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82)
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
- 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?)
- 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 Properties of Matrices of Zeros and Ones
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Generating Random Regular Graphs Quickly
- Generating random regular graphs
- 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 Regular Graphs and a Peer-to-Peer Network
- Sampling binary contingency tables with a greedy start
- The Factors of Graphs
- Uniform generation of random regular graphs of moderate degree
Cited in
(17)- On random sampling in uniform hypergraphs
- The mixing time of switch Markov chains: a unified approach
- New classes of degree sequences with fast mixing swap Markov chain sampling
- Uniform sampling of directed and undirected graphs conditional on vertex connectivity
- On the Complexity of Sampling Vertices Uniformly from a Graph
- The connectivity of graphs of graphs with self-loops and a given degree sequence
- Uniform random sampling of planar graphs in linear time
- Mixing time of the switch Markov chain and stable degree sequences
- Constructing and sampling directed graphs with given degree sequences
- Uniform sampling of bipartite graphs with degrees in prescribed intervals
- Switching edges to randomize networks : What goes wrong and how to fix it
- Parallel and I/O-efficient randomisation of massive networks using global curveball trades
- The switch Markov chain for sampling irregular graphs and digraphs
- On the swap-distances of different realizations of a graphical degree sequence
- Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
- Engineering uniform sampling of graphs with a prescribed power-law degree sequence
- 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)
