Connectivity of a general class of inhomogeneous random digraphs

DOI10.1002/RSA.20892MaRDI QIDQ5113954zbMATH OpenOpenAlexFDO

Authors Junyu Cao, Mariana Olvera-Cravioto

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.03319

zbMATH Keywords

scale-free graphsmultitype branching processescouplingsinhomogeneous random graphsrandom digraphskernel-based random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26)

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 Erdos-Renyi model, graphs with given expected degrees, the generalized random graph, and the Poissonian random graph. We establish the 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.

Recommendations

• Birth of a strongly connected giant in an inhomogeneous random digraph
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• scientific article; zbMATH DE number 4029600
• The phase transition in inhomogeneous random graphs
• The strong giant in a random digraph

Cited in

(16)

• Large dicliques in a directed inhomogeneous random graph
• Connectivity of Poissonian inhomogeneous random multigraphs
• Efficient presolving methods for the influence maximization problem
• Birth of a strongly connected giant in an inhomogeneous random digraph
• Universality for the directed configuration model: metric space convergence of the strongly connected components at criticality
• Giant components in three-parameter random directed graphs
• SIR model for households
• A classification of isomorphism-invariant random digraphs
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• Connectedness of graphs generated by a random d-process
• Modeling household effects in epidemics
• On the degree properties of generalized random graphs
• The limiting probability that \(\alpha\)-in, \(\beta\)-out is strongly connected
• A note on thresholds and connectivity in random directed graphs
• Local weak convergence for PageRank
• PageRank's behavior under degree correlations

This page was built for publication: Connectivity of a general class of inhomogeneous random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113954)