Unbiased degree-preserving randomisation of directed binary networks

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. ...

Graphs are used in many disciplines to model the relationships that exist between objects in a complex discrete system. Researchers may wish to compare a network of interest to a "typical" graph from a family (or ensemble) of graphs which are similar in some way. One way to do this is to take a sample of several random graphs from the family, to gather information about what is "typical". Hence there is a need for algorithms which can generate graphs uniformly (or approximate...

Given two distributions F and G on the nonnegative integers we propose an algorithm to construct in- and out-degree sequences from samples of i.i.d. observations from F and G, respectively, that with high probability will be graphical, that is, from which a simple directed graph can be drawn. We then analyze a directed version of the configuration model and show that, provided that F and G have finite variance, the probability of obtaining a simple graph is bounded away from ...

We consider distributed networks, such as peer-to-peer networks, whose structure can be manipulated by adjusting the rules by which vertices enter and leave the network. We focus in particular on degree distributions and show that, with some mild constraints, it is possible by a suitable choice of rules to arrange for the network to have any degree distribution we desire. We also describe a mechanism based on biased random walks by which appropriate rules could be implemented...

Directed acyclic graphs are the basic representation of the structure underlying Bayesian networks, which represent multivariate probability distributions. In many practical applications, such as the reverse engineering of gene regulatory networks, not only the estimation of model parameters but the reconstruction of the structure itself is of great interest. As well as for the assessment of different structure learning algorithms in simulation studies, a uniform sample from ...

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...

With complex networks emerging as an effective tool to tackle multidisciplinary problems, models of network generation have gained an importance of their own. These models allow us to extensively analyze the data obtained from real-world networks, study their relevance and corroborate theoretical results. In this work, we introduce methods, based on degree preserving rewiring, that can be used to tune the clustering and degree-correlations in directed networks with random and...

Many real-world networks exhibit correlations between the node degrees. For instance, in social networks nodes tend to connect to nodes of similar degree. Conversely, in biological and technological networks, high-degree nodes tend to be linked with low-degree nodes. Degree correlations also affect the dynamics of processes supported by a network structure, such as the spread of opinions or epidemics. The proper modelling of these systems, i.e., without uncontrolled biases, r...

Although asymptotic analyses of undirected network models based on degree sequences have started to appear in recent literature, it remains an open problem to study statistical properties of directed network models. In this paper, we provide for the first time a rigorous analysis of directed exponential random graph models using the in-degrees and out-degrees as sufficient statistics with binary as well as continuous weighted edges. We establish the uniform consistency and th...

The random graph of Erdos and Renyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian...