Directed random graphs with given degree distributions

Abstract

Given two distributions F and G on the nonnegative integers wepropose an algorithm to construct in- and out-degree sequences fromsamples of i.i.d. observations from F and G, respectively, thatwith high probability will be graphical, that is, from which a simpledirected graph can be drawn. We then analyze a directed version of theconfiguration model and show that, provided that F and G havefinite variance, the probability of obtaining a simple graph is boundedaway from zero as the number of nodes grows. We show that conditionalon the resulting graph being simple, the in- and out-degreedistributions are (approximately) F and G for large size graphs.Moreover, when the degree distributions have only finite mean we showthat the elimination of self-loops and multiple edges does notsignificantly change the degree distributions in the resulting simplegraph.

Keywords

• Directed random graphs
• simple graphs
• configuration model
• prescribed degree distributions