Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T14:16:54.426Z Has data issue: false hasContentIssue false
  • English
  • Français

Birth of a Strongly Connected Giant in an Inhomogeneous Random Digraph

Part of: Operations research and management science Markov processes Graph theory

Published online by Cambridge University Press:  04 February 2016

Mindaugas Bloznelis ,
Friedrich Götze  and
Jerzy Jaworski
Mindaugas Bloznelis*
Affiliation:
Vilnius University
Friedrich Götze*
Affiliation:
Bielefeld University
Jerzy Jaworski*
Affiliation:
Adam Mickiewicz University
*
∗ Postal address: Vilnius University, Naugarduko 24, LT-03225 Vilnius, Lithuania. Email address: [email protected]
∗∗ Postal address: Faculty of Mathematics, Bielefeld University, D-33501 Bielefeld, Germany. Email address: [email protected]
∗∗∗ Postal address: Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland. Email address: [email protected]
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.

We present and investigate a general model for inhomogeneous random digraphs with labeled vertices, where the arcs are generated independently, and the probability of inserting an arc depends on the labels of its endpoints and on its orientation. For this model, the critical point for the emergence of a giant component is determined via a branching process approach.

Keywords

Inhomogeneous digraphphase transitiongiant component

MSC classification

Primary: 05C80: Random graphs
Secondary: 90B15: Network models, stochastic 60J85: Applications of branching processes
Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 3 , September 2012 , pp. 601 - 611
Copyright
© Applied Probability Trust 

References

Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74, 47–97.Google Scholar
Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31, 3–122.CrossRefGoogle Scholar
Cooper, C. and Frieze, A. (2004). The size of the largest strongly connected component of a random digraph with a given degree sequence. Combinatorics Prob. Comput. 13, 319–337.CrossRefGoogle Scholar
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), 4 pp.Google Scholar
Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press.Google Scholar
Harris, T. E. (1963). The Theory of Branching Processes. Springer, Berlin.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2001). Random Graphs. John Wiley, New York.Google Scholar
Karp, R. M. (1990). The transitive closure of a random digraph. Random Structures Algorithms 1, 73–93.CrossRefGoogle Scholar
Łuczak, T. (1990). The phase transition in the evolution of random digraphs. J. Graph Theory 14, 217–223.CrossRefGoogle Scholar
Łuczak, T. and Cohen, J. E. (1992). Giant components in three-parameter random directed graphs. Adv. Appl. Prob. 24, 845–857.Google Scholar
Łuczak, T. and Seierstad, T. G. (2009). The critical behavior of random digraphs. Random Structures Algorithms 35, 271–293.Google Scholar
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, 17 pp.Google Scholar
Söderberg, B. (2002). General formalism for inhomogeneous random graphs. Phys. Rev. E 66, 066121, 6 pp.Google Scholar