Academic Journals Database
Disseminating quality controlled scientific knowledge

Directed random graphs with given degree distributions

ADD TO MY LIST
 
Author(s): Ningyuan Chen | Mariana Olvera-Cravioto

Journal: Stochastic Systems
ISSN 1946-5238

Volume: 3;
Issue: 1;
Start page: 147;
Date: 2013;
Original page

Keywords: Directed random graphs | simple graphs | configuration model | prescribed 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.
Why do you need a reservation system?      Affiliate Program