Directed Random Graphs with given Degree Distributions
By Ningyuan Chen, Mariana Olvera-Cravioto. 2012
75 citations recorded by the source corpus.
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 zero as the number of nodes grows. We show that conditional on the resulting graph being simple, the in- and out-degree distributions are (approximately) F and G for large size graphs. Moreover, when the degree distributions have only finite mean we show that the elimination of self-loops and multiple edges does not significantly change the degree distributions in the resulting simple graph.
Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics
View Paper: https://www.semanticscholar.org/paper/3fc2d163ec9dcd3db46b92e0ebde627be7b1df16
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Geometry and Topology
In Statistical and Nonlinear Physics
Citations in the corpus
- Random Graphs and Complex Networks (2016, methodology): “The degree structure of the directed configuration model, as well as ways to simulate it, are discussed by Chen and Olvera-Cravioto in [70].”