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.

Tango Rapperswil
Tango Rapperswil

    

Easyplan
HR software für Hotellerie

Automatische Erstellung
von Personaldokumente
und Anmeldungen bei Behörden