Constructing and sampling directed graphs with given degree sequences
From MaRDI portal
Abstract: The interactions between the components of complex networks are often directed. Proper modeling of such systems frequently requires the construction of ensembles of digraphs with a given sequence of in- and out-degrees. As the number of simple labeled graphs with a given degree sequence is typically very large even for short sequences, sampling methods are needed for statistical studies. Currently, there are two main classes of methods that generate samples. One of the existing methods first generates a restricted class of graphs, then uses a Markov Chain Monte-Carlo algorithm based on edge swaps to generate other realizations. As the mixing time of this process is still unknown, the independence of the samples is not well controlled. The other class of methods is based on the Configuration Model that may lead to unacceptably many sample rejections due to self-loops and multiple edges. Here we present an algorithm that can directly construct all possible realizations of a given bi-degree sequence by simple digraphs. Our method is rejection free, guarantees the independence of the constructed samples, and provides their weight. The weights can then be used to compute statistical averages of network observables as if they were obtained from uniformly distributed sampling, or from any other chosen distribution.
Recommendations
- Constructing and sampling graphs with a prescribed joint degree distribution
- Sampling k-partite graphs with a given degree sequence
- Uniform sampling of digraphs with a fixed degree sequence
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Towards random uniform sampling of bipartite graphs with given degree sequence
- A linear-time algorithm for sampling graphs with given degrees
- Sampling hypergraphs with given degrees
- Uniform sampling of directed and undirected graphs conditional on vertex connectivity
- Exact sampling of graphs with prescribed degree correlations
- Fast uniform generation of random graphs with given degree sequences
Cites work
- A critical point for random graphs with a given degree sequence
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A remark on the existence of finite graphs
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- 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
- Complex networks: structure and dynamics
- Complex networks. Papers from the conference `complex networks: structure, dynamics, and function', 23rd annual conference of the Center for Nonlinear Studies, Santa Fe, NM, USA, May 12--16, 2003.
- Computing and Combinatorics
- Connected components in random graphs with given expected degree sequences
- Degree-based graph construction
- Dynamical Processes on Complex Networks
- Generating simple random graphs with prescribed degree distribution
- scientific article; zbMATH DE number 4089545 (Why is no real title available?)
- scientific article; zbMATH DE number 3182201 (Why is no real title available?)
- scientific article; zbMATH DE number 3549966 (Why is no real title available?)
- scientific article; zbMATH DE number 1334601 (Why is no real title available?)
- scientific article; zbMATH DE number 1782878 (Why is no real title available?)
- scientific article; zbMATH DE number 1866312 (Why is no real title available?)
- Networks, crowds and markets. Reasoning about a highly connected world.
- Networks. An introduction.
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Sampling Regular Graphs and a Peer-to-Peer Network
- Sequences with a unique realization by simple graphs
- Switchings Constrained to 2-Connectivity in Simple Graphs
- The asymptotic number of labeled graphs with given degree sequences
- The structure and dynamics of networks
- Zero-one matrices with zero trace
Cited in
(18)- The Zipf-Poisson-stopped-sum distribution with an application for modeling the degree sequence of social networks
- Half-regular factorizations of the complete bipartite graph
- Universal construction mechanism for networks from one-dimensional symbol sequences
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- Sufficient conditions for graphicality of bidegree sequences
- Uniform sampling of digraphs with a fixed degree sequence
- Unbiased sampling of network ensembles
- Construction of directed assortative configuration graphs
- Network community detection using modularity density measures
- 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
- Constructing and sampling graphs with a prescribed joint degree distribution
- Methods for the graph realization problem
- MCMC sampling of directed flag complexes with fixed undirected graphs
- Statistical mechanics of random hyperbolic graphs within the fermionic maximum-entropy framework
- Fast and accurate determination of modularity and its effect size
- The configuration model for partially directed graphs
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
This page was built for publication: Constructing and sampling directed graphs with given degree sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5137614)
