Constructing and sampling directed graphs with given degree sequences

We provide asymptotic formulae for the numbers of bipartite graphs with given degree sequence, and of loopless digraphs with given in- and out-degree sequences, for a wide range of parameters. Our results cover medium range densities and close the gaps between the results known for the sparse and dense ranges. In the case of bipartite graphs, these results were proved by Greenhill, McKay and Wang in 2006 and by Canfield, Greenhill and McKay in 2008, respectively. Our method a...

One of the simplest ways to decide whether a given finite sequence of positive integers can arise as the degree sequence of a simple graph is the greedy algorithm of Havel and Hakimi. This note extends their approach to directed graphs. It also studies cases of some simple forbidden edge-sets. Finally, it proves a result which is useful to design an MCMC algorithm to find random realizations of prescribed directed degree sequences.

Random graphs (or networks) have gained a significant increase of interest due to its popularity in modeling and simulating many complex real-world systems. Degree sequence is one of the most important aspects of these systems. Random graphs with a given degree sequence can capture many characteristics like dependent edges and non-binomial degree distribution that are absent in many classical random graph models such as the Erd\H{o}s-R\'{e}nyi graph model. In addition, they h...

Designing algorithms that generate networks with a given degree sequence while varying both subgraph composition and distribution of subgraphs around nodes is an important but challenging research problem. Current algorithms lack control of key network parameters, the ability to specify to what subgraphs a node belongs to, come at a considerable complexity cost or, critically, sample from a limited ensemble of networks. To enable controlled investigations of the impact and ro...

Complex systems, ranging from soft materials to wireless communication, are often organised as random geometric networks in which nodes and edges evenly fill up the volume of some space. Studying such networks is difficult because they inherit their properties from the embedding space as well as from the constraints imposed on the network's structure by design, for example, the degree sequence. Here we consider geometric graphs with a given distribution for vertex degrees and...

We investigate the joint distribution of the vertex degrees in three models of random bipartite graphs. Namely, we can choose each edge with a specified probability, choose a specified number of edges, or specify the vertex degrees in one of the two colour classes. This problem can alternatively be described in terms of the row and sum columns of random binary matrix or the in-degrees and out-degrees of a random digraph, in which case we can optionally forbid loops. It can al...

When the network is reconstructed, two types of errors can occur: false positive and false negative errors about the presence or absence of links. In this paper, the influence of these two errors on the vertex degree distribution is analytically analysed. Moreover, an analytic formula of the density of the biased vertex degree distribution is found. In the inverse problem, we find a reliable procedure to reconstruct analytically the density of the vertex degree distribution o...

We propose a slightly revised Miller-Hagberg (MH) algorithm that efficiently generates a random network from a given expected degree sequence. The revision was to replace the approximated edge probability between a pair of nodes with a combinatorically calculated edge probability that better captures the likelihood of edge presence especially where edges are dense. The computational complexity of this combinatorial MH algorithm is still in the same order as the original one. ...

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g. to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes, called edge switches, to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate un...

This paper introduces new efficient algorithms for two problems: sampling conditional on vertex degrees in unweighted graphs, and sampling conditional on vertex strengths in weighted graphs. The algorithms can sample conditional on the presence or absence of an arbitrary number of edges. The resulting conditional distributions provide the basis for exact tests. Existing samplers based on MCMC or sequential importance sampling are generally not scalable; their efficiency degra...