Constructing and sampling directed graphs with given degree sequences

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.

20 pages, 5 figures

References in corpus (5)

• Generating simple random graphs with prescribed degree distribution
• The entropy of network ensembles
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• All scale-free networks are sparse
• Entropies of complex networks with hierarchically constrained topologies

Cited by in corpus (25)

• The structure and dynamics of multilayer networks
• The Statistical Physics of Real-World Networks
• Emergence of bimodality in controlling complex networks
• Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
• Quantifying randomness in real networks
• Visibility of minorities in social networks
• Low Algorithmic Complexity Entropy-deceiving Graphs
• Asymptotics in directed exponential random graph models with an increasing bi-degree sequence
• Exploratory Adaptation in Large Random Networks
• Looplessness in networks is linked to trophic coherence
• Degree correlations in directed scale-free networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Evolution of the Internet k-dense structure
• Sampling motif-constrained ensembles of networks
• Endemic infections are always possible on regular networks
• Diversity of structural controllability of complex networks with given degree sequence
• A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix
• Phase transitions for scaling of structural correlations in directed networks
• Grand canonical ensembles of sparse networks and Bayesian inference
• Connectedness matters: Construction and exact random sampling of connected graphs
• Mechanisms for tuning clustering and degree-correlations in directed networks
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Temporal-varying failures of nodes in networks
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles