Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-28T04:15:21.780Z Has data issue: false hasContentIssue false
  • English
  • Français

The strong giant in a random digraph

Published online by Cambridge University Press:  24 March 2016

Mathew D. Penrose
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider a random directed graph on n vertices with independent and 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.

Keywords

Semi-homogeneous random digraphgiant componentbranching process
Type
Research Papers
Information
Journal of Applied Probability , Volume 53 , Issue 1 , March 2016 , pp. 57 - 70
Copyright
Copyright © Applied Probability Trust 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bloznelis, M., Götze, F. and Jaworski, J. (2012). Birth of a strongly connected giant in an inhomogeneous random digraph. J. Appl. Prob. 49, 601–611. Google Scholar
[2]Bollobás, B. (2001). Random Graphs, 2nd edn. Cambridge University Press. Google Scholar
[3]Broder, A.et al. (2000). Graph structure in the Web. Comput. Networks 33, 309–320. Google Scholar
[4]Comets, F., Delarue, F. and Schott, R. (2014). Information transmission under random emission constraints. Combin. Prob. Comput. 23, 973–1009. Google Scholar
[5]Cooper, C. and Frieze, A. (2004). The size of the largest strongly connected component of a random digraph with a given degree sequence. Combin. Prob. Comput. 13, 319–337. Google Scholar
[6]Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. (2001). Giant strongly connected component of directed networks. Phys. Rev. E 64, 025101(R). Google Scholar
[7]Feller, W. (1968). An Introduction to Probability Theory and Its Applications, Vol. I, 3rd edn. John Wiley, New York. Google Scholar
[8]Fenner, T. I. and Frieze, A. M. (1982). On the connectivity of random m-orientable graphs and digraphs. Combinatorica 2, 347–359. Google Scholar
[9]Newman, M. E. J., Strogatz, S. H. and Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118. Google Scholar