Connectivity of a general class of inhomogeneous random digraphs
- 29 October 2019
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 56 (3) , 722-774
Abstract
We study a family of directed random graphs whose arcs are sampled independently of each other, and are present in the graph with a probability that depends on the attributes of the vertices involved. In particular, this family of models includes as special cases the directed versions of the Erdős‐Rényi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish a phase transition for the existence of a giant strongly connected component and provide some other basic properties, including the limiting joint distribution of the degrees and the mean number of arcs. In particular, we show that by choosing the joint distribution of the vertex attributes according to a multivariate regularly varying distribution, one can obtain scale‐free graphs with arbitrary in‐degree/out‐degree dependence.Keywords
This publication has 30 references indexed in Scilit:
- Birth of a Strongly Connected Giant in an Inhomogeneous Random DigraphJournal of Applied Probability, 2012
- Edge-based compartmental modelling for infectious disease spreadJournal of The Royal Society Interface, 2011
- An overview of semi-continuity results on the spectral radius and positivityJournal of Mathematical Analysis and Applications, 2008
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- On a conditionally Poissonian graph processAdvances in Applied Probability, 2006
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- The structure of a random graph at the point of the phase transitionTransactions of the American Mathematical Society, 1994
- Giant components in three-parameter random directed graphsAdvances in Applied Probability, 1992
- The phase transition in the evolution of random digraphsJournal of Graph Theory, 1990
- The transitive closure of a random digraphRandom Structures & Algorithms, 1990