Hostname: page-component-745bb68f8f-g4j75 Total loading time: 0 Render date: 2025-02-06T09:31:05.307Z 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
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 

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