The strong giant in a random digraph

2014/09/15 by Mathew D. Penrose, Penrose, Mathew D.
Mathematics · Physics and Astronomy · #05C80 #60J85 #92D30 #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1409.4371

openalex publication_date 2014/09/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider a random directed graph on n vertices with independent identically distributed outdegrees with distribution F having mean μ, and destinations of arcs selected uniformly at random. We show that if μ>1 then for large n there is very likely to be a unique giant strong component with proportionate size given as the product of two branching process survival probabilities, one with offspring distribution F and the other with Poisson offspring distribution with mean μ. If μ≤ 1 there is very likely to be no giant strong component. We also extend this to allow for F varying with n.

Related

• Birth of a strongly connected giant in an inhomogeneous random digraph
• Asymptotic distribution of the numbers of vertices and arcs of the giant\n strong component in sparse random digraphs
• Are giants in random digraphs `almost' local?
• On a general class of inhomogeneous random digraphs
• Multipartite random graphs with given degrees: local limit, revisiting the giant, distances